Hash table clustering

Why does a hash table's lookup cost explode while most of its slots are still sitting empty?

A hash table promises lookup in constant time, and for most of its life it delivers. Then, past the point where it is comfortably more than half full, the cost stops being flat and climbs steeply — and it does so while a tenth of the slots are still empty. A tenth of a million slots is a hundred thousand free homes.

Why should having somewhere to put things not be enough? The answer has nothing to do with running out of room, and everything to do with where the empty slots are.

Start with what a hash function does. It maps a key to a slot, scattering keys as if at random. Collisions are therefore not an accident but a certainty long before the table is near full — the same counting that makes shared birthdays likely in a room of twenty-three makes collisions likely in a million-slot table once a few thousand keys are in. So the question is never "why do keys collide" but "what does a collision cost".

Take open addressing: on a collision, probe onward until an empty slot appears. Suppose each key gets its own independent random order of slots to try — the idealisation called uniform hashing. Write the load factor as a. Each probe lands on an occupied slot with probability roughly a, so the count before hitting an empty one is geometric with expectation 1/(1 − a): 2 probes at a = 0.5, 10 at 0.9, 20 at 0.95. A climb — but note what drives it: not scarcity of slots, but the chance of finding one, 1 − a per attempt.

Now use the probe sequence almost everyone actually uses: linear probing, meaning try the next slot, then the next. Knuth's classic analysis — I am recalling the standard result rather than deriving it — gives the expected probes for an unsuccessful search as about half of (1 + 1/(1 − a)²). At 0.5 that is 2.5, barely worse than the ideal 2. At 0.9 it is 50.5, five times the ideal 10. At 0.95, 200.5 against 20.

Something is squaring. What?

Think about what linear probing does to adjacency. A colliding key does not fly off to an independent slot; it lands next to the run of occupied slots it hit. So runs form. A run of length L swallows any key whose home slot falls anywhere in it — L chances out of the table size — so a run grows at a rate proportional to its own length, and long runs lengthen fastest; two runs separated by one free slot eventually merge. Meanwhile a key landing in a run of length L must walk, on average, half of it. Runs grow in proportion to length and cost in proportion to length, and multiplying those two dependencies is where the square comes from. This is primary clustering.

Notice the mean occupancy is still a everywhere. What changed is the distribution: free slots stopped being spread out and started being bunched, and a bunched free slot is no use to a key whose home lies mid-run.

Let us test that. If adjacency is the cause, then keeping everything identical — same keys, table, load factor, hash function — and changing only the probe sequence should collapse the cost. Double hashing does exactly that: the step size comes from a second hash, so two keys sharing a home slot diverge immediately and never form a run. Its expected unsuccessful cost is the ideal 1/(1 − a): 10 probes at 0.9 rather than 50. That prediction holds. The refuting observation is equally clear: if double hashing still cost around 50 probes at 0.9, adjacency was innocent and the hash function's distribution would be the culprit instead.

There is a second, quieter reason a table can be mostly empty and still slow. In open addressing you cannot blank a slot on deletion — that would truncate some other key's probe sequence, making it unfindable. So deletions leave tombstones: markers counting as occupied for searching and free for inserting. A churning table accumulates them, so its search load factor can approach 1 while few entries are live — every slot genuinely available, the table behaving as if full, until a rebuild sweeps them out.

The misconception to correct is that the load factor measures space. It does not; it measures the probability that a probe fails, and cost is that probability compounded across probes. Hence a hyperbola rather than a line, and hence the last few per cent of a table costing more than the first eighty combined.

Two honest qualifications. First, every formula above assumes the hash function scatters keys as if uniformly at random. A poor one produces clustering of a worse kind — keys piling on the same home slot — which no probing scheme rescues, and real keys such as sequential integers or aligned pointers trigger it easily. Second, linear probing's bad asymptotics have not made it obsolete, because the binding constraint is often not the probe count but the memory hierarchy: a linear probe walks contiguous memory, so a whole run may arrive in one cache line, while double hashing's scattered steps pay a miss each. That is why linear probing usually wins in practice provided the load factor is kept near a half. The mathematics says avoid clustering, the hardware says favour locality, and the resolution — keep the table sparse enough that runs stay short — will outlive any particular implementation.

• Why Robin Hood and cuckoo hashing bound the worst-case probe length rather than merely improving the average.
• How a table resizes without a long stall, and what incremental rehashing costs in exchange.

Every term the collection defines is gathered in the glossary.