The probe nobody waits for

A hash table with open addressing puts a key at the slot its hash names, and if that slot is taken it walks forward until it finds an empty one. How far it walked is the key’s displacement, and a lookup for that key costs one more probe than its displacement.

The trouble with plain linear probing is that displacement is unfairly distributed. An early arrival keeps a slot it barely wanted; a later arrival walks past it and past twenty others. At a load factor of 0.95 in a table of 512 slots, the worst-displaced key sits 114 slots from home, and the key immediately after it in memory may sit at zero.

Robin Hood hashing fixes that with one rule: when the key being inserted has walked further than the key occupying the slot, they swap, and the richer key carries on looking.

The mean cannot move, and this is why #

The most useful thing about Robin Hood hashing is a fact about it that requires no measurement at all.

Fix a set of keys and a hash function. The set of slots the keys hash to is fixed. The set of slots they occupy is fixed too — a table with $n$ keys in $m$ slots has the same $n$ occupied slots whichever insertion policy is used, provided the policy is a permutation of who sits where. So $\sum(\text{occupied slot} - \text{home slot})$ is the same number under any such policy.

Robin Hood is exactly such a policy: it never changes which slots are occupied, only which key is in which. So the total displacement is invariant and the mean is invariant.

That is a theorem and this site’s habit is to check theorems rather than repeat them. assertRobinHoodMovesVarianceNotMean requires the two means to agree to within $10^{-9}$ and fails the build if they do not. It has a second clause requiring the variance to at least halve, because a policy that left the variance alone would satisfy the first clause by doing nothing.

At every load the mean is shared between the two columns because it must be. At load 0.95 the worst case improves by a factor of 5.75 and the variance by a factor of 10.3.

Why an average was the wrong summary all along #

The probe formula nobody checks is about Knuth’s expression for the expected number of probes in a linear-probing table:

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

at load factor $\alpha$. That essay measured it, found it accurate for random keys, and found it wildly wrong for keys whose stride shares a factor with the capacity. What it did not say — because the site had no way to say it — is that the formula is an expectation, and the expectation is not what a hash table’s user experiences.

A program doing a million lookups in a table at load 0.95 does not experience 5.817 probes. It experiences 5.817 probes on average, with individual lookups ranging from 1 to 115, and the ones at 115 are the ones that show up in a latency percentile. If the table is behind a request, the 99th percentile of the response time is a function of the tail of that distribution and not of its mean.

Robin Hood improves exactly the quantity that matters and leaves exactly the quantity that gets reported unchanged. That is not a coincidence; it is the design. And it means a benchmark reporting mean lookup time would measure the two as identical, which is very close to what happened historically — the technique was published by Celis in 1986 and was largely ignored for twenty-five years, until latency percentiles became the thing systems people measured.

The cost, and where it goes #

The rule is not free. Each swap during insertion is a write, and at load 0.95 in a 512-slot table there are 1,224 swaps for 486 keys — about two and a half per insertion.

That is the trade and it is the usual shape: more work when writing, less variance when reading. For a table built once and queried many times it is clearly worth it. For a table with a high update rate and no latency requirement, it is not obviously anything.

There is a second and less obvious cost that this site cannot measure and should name. Robin Hood’s insertion carries a key in hand and swaps it repeatedly, which means the write pattern is a chain of dependent stores rather than one store — and dependent stores do not pipeline. The write count is a poor proxy for the write cost here, in the same way the comparison count is a poor proxy for a merge’s cost in the branch the machine guesses.

There is also a benefit the counters do not see. Because every key’s displacement is bounded by a small number, a lookup can stop early: if the current slot’s displacement is less than how far the search has walked, the key being sought cannot be present, because it would have stolen this slot. Plain linear probing has no such test and must walk to the next empty slot. On a lookup for an absent key that is a large saving and it is invisible to a probe count over present keys.

Where the variance comes from #

Understanding why the distributions differ so much requires one idea, and it is the same one that makes linear probing fast in the first place.

Linear probing forms clusters: runs of consecutive occupied slots. A key hashing anywhere into a cluster of length $L$ must walk to the end of it, so the expected displacement is proportional to the cluster length, and clusters grow superlinearly with load because a new key landing anywhere in a cluster extends it and merges it with the next.

That is the mechanism behind the $1/(1-\alpha)^2$ in the formula: it is a statement about cluster lengths, and cluster lengths are heavy-tailed.

Robin Hood does not break up the clusters — the occupied slots are the same slots, so the clusters are identical. It redistributes the displacement within each cluster, so that instead of one key at the far end paying for the whole cluster’s length, every key in it pays about the average. The cluster length distribution is unchanged; the per-key cost distribution is flattened against it.

That framing explains the table above precisely. At low load the clusters are short and there is little to redistribute; at high load they are long and the redistribution is worth a factor of ten in variance.

Deletion, which is where open addressing usually goes wrong #

Every discussion of open addressing eventually reaches deletion, and it is where the design is at its least elegant.

A key cannot simply be removed. Emptying its slot breaks the probe sequence of every key that walked past it: a lookup for one of those keys would reach the newly empty slot, conclude the key is absent, and be wrong. The standard answer is a tombstone — a marker meaning “occupied for the purpose of continuing, empty for the purpose of inserting” — and tombstones accumulate, so a table that has seen many deletions has an effective load factor above its actual one and eventually has to be rebuilt.

Robin Hood removes the need for tombstones entirely, and the mechanism is the same invariant that flattens the distribution.

Because every key sits at or after its home slot and displacements decrease with distance from a cluster’s start, deleting a key can be repaired by shifting back: take the next key, and if its displacement is greater than zero, move it into the hole and repeat. Stop at the first key whose displacement is zero, because that key is at home and nothing walked past the hole to reach it.

The result is a table with no tombstones, whose load factor is exactly its occupancy, and which never needs rebuilding for that reason. A property of the distribution — that displacements decrease along a cluster — turns into a property of the data structure’s lifecycle, and neither is visible in a probe count.

This site does not measure deletion, and saying so is the point of the paragraph. The counters here are built around insertions and lookups; a structure’s behaviour under a workload of mixed operations over time is a different subject with a different instrument, and it is the one where hash tables in real systems actually spend their difficulty.

The lookup this essay did not measure #

Every number above is about keys that are present. The early-stop test is named as a benefit the counters miss, and it is worth pricing, because on the other kind of lookup it is not a refinement — it is the largest effect on the page.

A plain linear-probing search for an absent key cannot stop until it reaches an empty slot, so it walks the whole remaining cluster. The classical expressions say what that costs:

$$\text{present} \approx \tfrac12\left(1 + \tfrac{1}{1-\alpha}\right), \qquad \text{absent} \approx \tfrac12\left(1 + \tfrac{1}{(1-\alpha)^2}\right)$$

At a load factor of 0.75 the ratio between them is 3.4. At 0.95 it is nineteen. An unsuccessful lookup in a nearly-full linear-probing table is an order of magnitude more expensive than a successful one, and every plate in this essay measures the cheaper of the two.

Robin Hood removes almost all of it. Because displacements decrease along a cluster, a search that has walked further than the current slot’s occupant can stop immediately: the sought key would have stolen that slot. So an absent lookup stops at about the mean displacement rather than at the end of the cluster, and its cost is close to a present lookup’s — six probes rather than two hundred, at the load where the gap is widest.

That makes the technique’s headline claim understated in a specific way. On present keys the mean is provably unchanged and only the variance moves, which is the essay’s central and slightly austere result. On absent keys the mean itself moves, by a factor that grows without bound as the table fills, and the invariance argument does not apply — because the two policies are no longer doing the same number of probes.

Two things follow that matter more than the variance for many deployments.

Absent lookups are common. A membership test that usually says no, a cache that usually misses, a deduplication check on mostly-new keys — all of them are dominated by the case this essay does not measure, and for all of them Robin Hood is a mean-time improvement rather than a tail one.

And it changes which load factor is affordable. The reason tables resize at 0.75 rather than 0.95 is the $1/(1-\alpha)^2$ in the absent-lookup expression, and Robin Hood replaces that term with something closer to $1/(1-\alpha)$. A structure whose unsuccessful search degrades linearly rather than quadratically can be run fuller, which is memory saved — and it is the same trade the last section describes, arriving from the operation this essay left out.

When the hash is the problem instead #

Everything above assumes the hash spreads the keys. A hash is a family, not a function is about what happens when it does not, and Robin Hood does not help there in the way it might appear to.

If every key hashes to the same slot, the cluster is the whole table. Robin Hood redistributes the displacement within it, so instead of one key at displacement $n-1$ and the rest spread below, every key sits at about $n/2$. The variance collapses, as advertised, and the mean is $n/2$ and the table is useless.

That is worth stating because “reduces the worst case” sounds like a defence against adversarial keys and it is not one. Robin Hood makes a table’s performance uniform; it does not make it good. Under an adversarial hash it makes every lookup equally terrible instead of most lookups fast and a few catastrophic — which for a latency percentile is arguably worse, since the bad case now happens on every request rather than on one in a thousand.

The defence against adversarial keys is a keyed hash family, and there is no structural substitute for it. Robin Hood addresses the variance that arises from randomness; nothing addresses variance that arises from an adversary except denying the adversary the information.

The load factor and the table size are the two dials, and the finding survives both. The means stay identical because the total displacement is decided by the hash; what moves is everything about the distribution.

What the libraries do #

Robin Hood hashing is the basis of several widely used tables — Rust’s hashbrown was originally Robin Hood before moving to SIMD probing, and a good many C++ open-addressing tables use it directly.

The dominant modern design, Google’s Swiss tables, does something related and different: it stores a byte of each key’s hash in a separate metadata array, and probes sixteen slots at a time with a vector comparison. That does not reduce displacement at all — it makes each probe sixteen times cheaper, which attacks the same problem from the other end.

Two techniques, the same symptom, opposite mechanisms. Robin Hood makes the number of probes uniform; Swiss tables make the probes cheap enough that the number stops mattering. Which is better depends on the same kind of hardware ratio that decided the branchless search — and, as there, this site can decompose the trade and cannot resolve it.

The load factor is the parameter that matters #

One number decides everything above, and it is not the hash and not the policy.

At load 0.5, plain linear probing’s worst displacement is 18 and Robin Hood’s is 6 — a factor of three, on a table where the mean displacement is 0.699 and almost every lookup is a single probe. At load 0.6 the numbers are the same to within one slot. At load 0.95 it is 114 against 19 on a table where the mean is 4.817.

The gap between the policies grows with the load, and so does the reason to care about it. At low load neither policy is doing much, because there is nothing to redistribute; at high load the redistribution is the difference between a usable table and one with a tail nobody can plan around.

Which reframes the design question. A table can buy a bounded worst case in two ways: keep the load low and rehash often, or keep the load high and use Robin Hood. The first costs memory — a table at load 0.5 is twice the size of one at 0.95 for the same keys — and the second costs writes. The insertion policy and the resize threshold are the same decision approached from two sides, and a library that has chosen one has constrained the other.

That is the same shape as the thresholds in the threshold somebody chose: a constant in a source file — the load factor at which the table doubles, 0.75 in Java, 0.66 in Python, 7/8 in Swiss tables — that decides more about the structure’s behaviour than the algorithm does, and that cannot be chosen independently of the rest.

The theorem is the check #

A closing note about method, because this essay’s central fact is unusual for this site.

Almost every claim here is granted by measurement: a class fits or it does not, a formula matches or it does not. This one is granted by an argument — the total displacement is fixed by which slots are occupied, so the mean cannot move — and the measurement’s role is to check the implementation against the theorem rather than to establish the theorem.

That is the right way round and it is worth being explicit about, because the two are easily confused. If the measured means had differed, the conclusion would not have been that the theorem is false. It would have been that robinHood has a bug — most likely losing a key or leaving a slot occupied that should not be — and the assertion’s error message says so.

A measurement that disagrees with a proof is a measurement of something else, and knowing which of the two is under test is the difference between a check and a coincidence.