The probe formula nobody checks

Under linear probing, the expected number of probes for an unsuccessful search — which is what an insertion is, since it probes until it finds an empty slot — at load factor $\alpha$ is

$$\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$$

and for a successful search it is

$$\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$$

These are Knuth’s results, they are in every reference, and they are the basis of the standard advice about keeping load factors below about 0.7. They are also almost never checked against a table.

Checking them takes twenty lines. Doing it turns up two things worth knowing: one about which formula applies, and one about how far a limit is from a finite object.

The wrong formula looks exactly like a broken hash #

The first version of the check on this site compared measured insertion costs against the successful-search formula. At a load factor of 0.7 the measurement came in 55% below the prediction.

A 55% discrepancy in a hash table check is alarming, and the natural first suspicion is the hash function. A hash that clusters badly would produce probe counts above the formula; one that somehow distributed better than uniform would be impossible; a bug in the probe counting would explain it. All plausible, all wrong.

The actual explanation is that inserting a key is an unsuccessful search. The insertion probes slots until it finds an empty one, which is precisely the search that fails, and the successful-search formula describes something else entirely — looking up a key that is already there, which on average stops halfway through its cluster.

The two forms differ by the square in the denominator. At $\alpha = 0.25$ they give 1.17 and 1.39: close enough that a check at low load would pass. At $\alpha = 0.85$ they give 3.83 and 22.72, a factor of six. The error is invisible where anyone would first test and glaring where the table gets full, which is the most dangerous shape a mistake can have.

The site’s gate now asserts both directions: the measurements must match the unsuccessful-search form to within 5%, and must fail to match the successful-search form. The second assertion exists so that a future refactor that reintroduced the confusion would be caught rather than quietly producing plausible numbers.

What the measurement says #

Averaged over eight independent fills of a table with 8,192 slots:

Both columns are means over the whole fill rather than instantaneous values at that load factor — an insertion into a table being filled to 0.9 experiences every load factor from 0 to 0.9 along the way, so the comparable quantity is the formula integrated over the fill.

Two things. The formula is accurate — within 3% everywhere, which for a closed-form model of a randomised process is excellent. And at the high-load end the measurements come in consistently below it, with the gap widening as the table fills.

That sign is not sampling noise. Noise would scatter either side of zero. A bias that appears only at high load and grows with it is a finite-size effect, and it is measurable.

How wrong the limit is #

Knuth’s formula is derived in the limit as the table size goes to infinity with $\alpha$ held fixed. A real table has 256 slots, or 8,192, and the formula applied to it is an approximation whose error depends on the size.

At $\alpha = 0.95$ and 256 slots, the measured mean is 48% below the formula. At 32,768 slots the discrepancy is a couple of percent. The condition for the asymptotic form to be trustworthy is roughly $m(1-\alpha)^3 \gg 1$, and at 256 slots with $\alpha = 0.95$ that product is 0.03 — three orders of magnitude outside the regime the derivation assumes.

The direction of the error is worth noting: the formula is pessimistic for small tables. Somebody sizing a table by it at high load would over-provision, which is the safer of the two ways to be wrong and is still an error of nearly a factor of two.

This is the same phenomenon as a complexity class that changes when the measurement range is extended, in a closed form rather than a class. A limit is a claim about a sequence and not a value for any member of it, and how far the two are apart is a separate question with a measurable answer.

Why the cost runs away #

The shape of the curve is the practical content of the formula, and it is worth reading directly.

Read instantaneously — the cost of one insertion into a table already at load $\alpha$ — the formula gives 1.5 probes at $\alpha = 0.5$, 50.5 at 0.9, and 200.5 at 0.95. The $(1-\alpha)^2$ in the denominator means the cost is not merely increasing as the table fills; it is increasing faster and faster, and the last few percent of capacity are catastrophic.

Averaged over a whole fill the numbers are much gentler — 1.50 to reach 0.5, 5.51 to reach 0.9 — because most of the insertions happened while the table was still empty. Both quantities are useful and they answer different questions: the integral gives what building the table costs, and the instantaneous value gives what the next insertion will cost. Quoting one when the other was meant is a factor of nine at $\alpha = 0.9$.

The mechanism is clustering, and it is specific to linear probing. When a key collides it takes the next slot, which makes that run of occupied slots one longer, which makes it a larger target for the next collision, which makes it longer still. Occupied runs grow superlinearly and a key hashing anywhere into a run must walk to its end.

This is why the standard advice is to resize at a load factor of 0.7 or thereabouts. It is not a magic number: it is the point where 2.2 probes per insertion is still cheap and the curve is about to stop being flat.

The hash is doing less work than it appears to #

A reasonable objection to all of this: surely the probe count depends on the hash function, so how can a single formula describe it?

The answer is that once the hash is even roughly uniform, the probe count is dominated by the load factor and barely notices the hash at all. The formula’s derivation assumes uniform hashing, and a decent multiplicative hash is close enough to uniform that the difference is inside the measurement noise.

What the formula cannot survive is a hash that is not roughly uniform, and the common way to get one is not to hash at all. Many implementations use the identity for integer keys, on the reasonable grounds that hashing an integer to another integer seems wasteful. Then consecutive keys — and consecutive keys are what real data supplies — land in consecutive slots, forming one enormous cluster, and the measured probe count departs from the formula badly.

The site’s check would catch that, because it compares against the formula rather than against itself. That is worth noting as a general property, and it is the same reason the sorting floor is computed two ways: a check against a closed form catches a class of bug that a check against a previous measurement cannot, because a previous measurement of a broken implementation is a broken baseline.

The alternatives, briefly #

Linear probing’s clustering is not the only option and the trade is worth stating.

Quadratic probing and double hashing step by a varying amount, so keys that collide do not follow the same subsequent path and clusters do not merge. Their probe counts at high load are much better than linear probing’s — double hashing’s unsuccessful-search cost is $\frac{1}{1-\alpha}$, which at $\alpha = 0.9$ is 10 against linear probing’s 50.5.

Chaining puts colliding keys in a list hanging off the slot — and inherits every problem a pointer-chasing structure has. The expected chain length is exactly $\alpha$ and there is no clustering at all, so performance degrades gracefully past a load factor of 1.

And linear probing is used anyway, in most high-performance implementations, for a reason this site is well placed to explain: its access pattern is sequential. A probe sequence walks to the next slot and the next, so a cluster of eight entries lives in one cache line and is fetched once. Double hashing’s probe sequence jumps, and every probe is a fresh cache miss; chaining follows pointers, which is worse still.

So the algorithm with the worst probe count has the best memory behaviour, and on modern hardware it usually wins. That is the two-counts problem again, and it is the reason the probe count alone was never going to settle the question.

Two routes, and why both are needed #

The site’s check requires the closed form and a filled table to agree. That is more than a test of the implementation.

The formula checks the implementation. If the hash clustered badly — if consecutive integer keys hashed to consecutive slots, which they do under an identity hash — the measured probe count would exceed the formula substantially, and the check would catch it.

The implementation checks the formula’s applicability. The formula is correct and its applicability to a table of a given size is not something the formula knows. Measuring is the only way to find out where the finite-size error becomes material, and the answer — that it is negligible at $\alpha = 0.5$ and nearly 50% at $\alpha = 0.95$ on a small table — is not derivable from the formula itself.

Neither route alone would give what the pair gives. This is the same discipline as computing the sorting floor twice, once by summation and once by Stirling: two independent routes to one number, where agreement is evidence about both.

What “expected” is promising here #

The probe formula is an expected cost, and it is worth being precise about what the expectation is over, because it is not the same thing as quicksort’s expected cost.

Quicksort with a random pivot takes its expectation over the algorithm’s own coin flips, so the bound holds on every input. Nothing an adversary supplies can make it likely to be slow.

A hash table’s expected probe count takes its expectation over the hash function’s behaviour on the keys, which is assumed to be uniform. If the hash is fixed and public, an adversary who knows it can compute keys that all collide, and the expectation is worthless — every insertion walks the whole cluster and the table degrades to a linked list. This is a real and exploited attack, and the defence is the same one quicksort uses: randomise. A hash seeded per process, unknown to the attacker, moves the expectation from being over an assumption about the keys to being over the algorithm’s own randomness, and restores the guarantee.

So the three-way distinction between average, expected and amortised has a fourth wrinkle inside “expected”: it matters whether the randomness belongs to the algorithm or is assumed about the input, and only the first kind survives an adversary.

What to take from this #

Three things, in increasing order of generality.

Use the right formula. Insertion is an unsuccessful search. The successful-search form describes lookups of keys that are present, and using it for sizing decisions understates the cost by a factor that grows as the table fills.

Check the formula’s regime. An asymptotic result applied to a small object has an error, and the error can be tens of percent. Measuring it takes an afternoon and the result is a number rather than a hope.

A quoted constant is a claim. Every published closed form in this subject can be checked against an implementation, and the checks are almost never done — not because they are hard but because the results are known, and once the answer is known, verifying feels like a formality. It is a formality until it is not, and the two things this essay reports were both found by doing it anyway.