Answers · Making it fast enough

Why can't a hash table give me the next key in order?

In shortBecause a good hash deliberately scatters neighbouring keys, so the table keeps no record of which key comes after which; finding the next key means reading every entry.

A hash table cannot hand you the next key in order because the hash destroys that order on the way in. A key's position is decided by its hash value, not by how it compares with any other key, so knowing where one key sits tells you nothing about where the key after it sits. There is a route from a key to its slot, and no route from a slot to the next key. Any question about neighbours, ranges, smallest or largest has to be answered by reading the whole table, which is precisely the cost the table was built to avoid.

FIG 1

key	0.618034 x key	fractional part	slot
1000	618.034	0.034	2
1001	618.652	0.652	41
1002	619.270	0.270	17
1003	619.888	0.888	56

Read the last column: 2, 41, 17, 56. The keys 1000 and 1001 are adjacent integers and their slots are 39 positions apart; 1001 and 1002 are 24 apart the other way; 1002 and 1003 are 39 apart. Nothing in the array of slots reflects the fact that these four keys are consecutive, and nothing in it reflects which of them is bigger. If you are standing at slot 41 holding key 1001, the array gives you no reason to look at slot 17 rather than slot 2, 3, 60 or 63. The next key could be anywhere, and on average it is halfway across the table.

Why a better hash will not fix it

The natural repair is to demand a hash that keeps neighbours together, and that repair is the one thing a hash may not do. A table with $m$ slots must map a huge key space into it: 32-bit keys give $2^{32} = 4{,}294{,}967{,}296$ possibilities, which over 64 slots is $4{,}294{,}967{,}296 / 64 = 67{,}108{,}864$ keys per slot, so the mapping cannot be one-to-one and certainly cannot be order preserving. And if it were, a million sequence numbers or timestamps would pile into a narrow band of slots, every lookup in that band would walk a chain as long as the band, and the constant-time promise would be gone. Real keys are structured, so a hash that respects their structure fails on exactly the data people store. The even spread and the lost order are the same property seen from two sides.

A partial patch shows the same thing. You could keep the keys inside each slot in sorted order, so that a chain is searchable in order. But the next key after 1001 is almost never in 1001's own slot: with 64 slots the chance that any particular other key shares a slot is $1/64$ , about 1.6 per cent, so roughly 98 per cent of the time the successor sits in a slot you had no reason to visit. Sorting the chains tidies up the inside of one slot and leaves the table as a whole unordered. The same applies to insertion order in a chain: it records when a key arrived, not what it is.

Growing the table makes it worse rather than better. When the load factor rises the slots are rebuilt at a new size, and every key moves to a position computed from the new $m$ . The slot number is a function of the table's current size, so it is not a stable property of the key and cannot be used as a sort key even in principle. A key that sat at slot 41 in a 64-slot table sits somewhere else entirely in a 128-slot one.

What the scan actually costs

Suppose a million keys and you want everything between 4,000,000 and 4,010,000. The dictionary has no choice: it tests all 1,000,000 entries against the bounds, one at a time, because there is no region of the array that corresponds to that interval of keys. A structure that keeps keys sorted does two binary searches instead, and each one needs about twenty comparisons, since halving a million items reaches a single one in twenty steps. It then walks only the few thousand items that fall inside the range.

2^{20} = 1{,}048{,}576 \ge 1{,}000{,}000 \quad\Rightarrow\quad \lceil \log_2 10^6 \rceil = 20

So locating one end of the range costs 20 comparisons in the sorted structure against 1,000,000 tests in the table, a factor of 50,000 before any of the wanted items are read. The table still wins the exact lookup, one step against twenty, and that trade is the whole decision: exact key only, use the table; anything phrased as next, previous, between, smallest or in order, keep something sorted. Real systems carry both, a hash index for equality and a tree or a sorted list for ranges, and pay for the second in memory and in bookkeeping on every write.

Where the complaint stops applying

The claim is about large tables and genuine order questions. With a few dozen keys, scanning all of them is cheaper in wall-clock time than twenty comparisons and a tree walk, and nobody should build an index for it. And if the keys are a dense range of small integers and the hash is the identity, the slot number happens to equal the key, so order survives by accident; that is an array wearing a hash table's name, and it stops being true the moment a key outside the range or a second dimension arrives. The moment the key set is sparse, or textual, or 64-bit, the accident is over.

Worth keeping

A hash table answers questions about one exact key and cannot answer questions about which keys are near it.
Keeping neighbouring keys in neighbouring slots would destroy the even spread that makes lookup cost constant.
A sorted structure finds a range's boundaries in about twenty comparisons for a million keys, where a hash table must read all million.

Where this goes next

This question is one step of Finding It Instantly, a course that works through its subject from the beginning. The page that teaches this part of it is What a Hash Table Cannot Do, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course