The question the index cannot answer
You have an index that answers in 1.3 comparisons. Ask it the simplest thing you can ask of a library: list the books alphabetically.
$ algo gen -n 1000 -seed 3
$ algo ordered -n 6
the first 6 titles, as the index stores them:
Lažižo
Rūdovi
Bąkėbėra Mąbą
Lėpubė
Žąčąva Šomū
Medošibe
the first 6 in alphabetical order:
Bagogū Guže
Bamežanė Pako
Bamila
Basėrūno
Batalu
Batėvovu Sūvi
getting the second list from the index cost a full sort of all 1000 keys.
the index itself could not answer the question at all.
The first list is not disordered by mistake. It is bucket order — which is
hashKey(title) % bucket count order, and the entire job of a hash function is to
destroy any relationship between a key and its number. That is precisely why the
chains stay short. The order was not lost — it was destroyed on purpose, and
that is what you paid.
The second list came from sorting all 1,000 keys. That is O(n log n) for every
such question — more expensive than everything the index ever saved.
What a hash table cannot do
Not "does slowly". Cannot.
| question | hash table |
|---|---|
| is "Bamila" there? | 1.3 comparisons |
| which is first alphabetically? | only by sorting everything |
| which start with "Ba"? | only by scanning everything |
| what are the 20 after "Bamila"? | not a concept it has |
| which book comes before this one? | not a concept it has |
| highest rating? | only by scanning everything |
The answer to every one of these is the same: go back to the whole collection. The index is no help, because it knows nothing about what follows what.
This is not a shortcoming
Step 1 said it: a structure buys one thing and pays with another. Here the trade is visible from both sides:
A hash table is the best thing you have for one question — "is this exact key present" — and it answers no other.
You would not choose it for a library catalogue that has to be shown a page at a time. You would choose it for a session store, a word-frequency counter, "is this username taken".
The question lesson 11 opens with
Lesson 11 starts from the second list in this step — but produces it without sorting anything.
A binary search tree gives up the O(1): its lookup costs O(log n), so it is
slower than your index. In exchange it keeps the order inside its own
structure, and walking from smallest to largest is a single traversal.
The question this index cannot answer at any price will, in lesson 11, cost O(n)
and not one comparison more than it takes to visit each element.
That is not "better". It is the other side of the trade.