Theory

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.