An insertion that can fail

Every randomised structure measured in this field so far makes the same kind of promise. A skip list’s search is expected $\log n$ and occasionally more. A hash table’s probe is expected constant and occasionally long. The second choice improves a tail without removing it.

Cuckoo hashing makes a different kind. A lookup examines exactly two slots. Not on average, not with high probability, not for these keys: for any keys, always, two.

The price is not paid at lookup time. It is paid at construction time, and it is not a cost — it is a probability of failure.

That difference is worth naming before the mechanism, because it changes what a reader should look for. A structure with an expected cost is evaluated by measuring its distribution — the mean, the spread, the tail — and this collection has instruments for all three. A structure with a construction that either works or does not is evaluated by measuring when it works, which is a different question with a different shape of answer: not a curve, but a location.

The structure, and where the randomness went #

Two tables, two hash functions, one slot per key in each.

A lookup computes both hashes and reads both slots. If the key is present it is in one of them, because those are the only two places it can be. Two reads, unconditionally, and the key’s presence or absence is decided.

An insertion tries the first slot. If it is free the key goes in and the insertion is over. If it is occupied, the incoming key takes the slot and the evicted key is re-placed in its other slot — which may in turn be occupied, evicting another key, and so on. The chain either finds a free slot and stops, or it goes round forever.

That last clause is the whole of the trade. Every other randomised structure here spreads its uncertainty across many operations, so a bad outcome is a slow operation among fast ones. This one concentrates all of it into one event: the construction succeeds, in which case every subsequent lookup is two probes, or it does not succeed and there is no table at all.

The repair when it fails is to draw two new hash functions and start again from scratch. That is expensive, it is rare below the threshold, and the amortised cost of insertion stays constant because the probability of having to start again falls fast enough — which is the standard analysis and is not what this page measures.

It is also worth noticing what the two-probe lookup does not require. It does not need the table to be sparse — a full table is fine to read. It does not need the hashes to be independent of the keys in any strong sense. It does not degrade as the table fills. All of the load-dependence is on the insertion side, so a table built once and read forever has a bound that never moves. A guarantee is not a result is the theme this collection has for the difference between a promise and a measurement, and this is the rare case where the promise is exact and the measurement is about whether it can be obtained at all.

The threshold is a threshold, not a slope #

The measured numbers on a five-hundred-slot table are already suggestive and they are not conclusive, because at that size the transition is smeared. What makes it a phase transition rather than a steep curve is what happens when the table grows.

Read across the bottom row and across the top. On a small table the failure rate rises gently; on a large one it goes from nothing at 0.45 to nineteen-in-twenty at 0.55. The transition sharpens with size, which is the signature of a genuine threshold and is not what a smooth dependence on load would do.

The published location is exactly one half: with two hash functions and one slot per bucket, a random cuckoo construction succeeds with probability approaching one below a load of 0.5 and approaching zero above it. The measurements straddle that, and the residual failures just below 0.5 on the small tables are the finite-size effect the sharpening is measuring away.

A structure whose guarantee holds below a load factor and not above one is a different kind of object from a structure whose cost degrades with load, and this is the only one in this collection. Every other load factor here is a dial — probes rise, chains lengthen, a filter’s error grows. This one is a cliff.

The measured location is a little above one half rather than at it, and the direction of the discrepancy is worth checking rather than waving at. Both effects that could produce it push the same way. A displacement limit — the implementation gives up after a stated number of evictions rather than looping forever — turns some constructions that would eventually have succeeded into failures, which pushes the measured threshold down. A finite table smears the transition in both directions. The measured rates below 0.5 on the small tables are the smearing; the fact that they vanish as the table grows is the evidence that the underlying location is where the theory puts it.

Why the chain stops terminating #

The mechanism is a graph and it is worth seeing, because it explains both the threshold and its sharpness.

Take each slot as a vertex and each key as an edge joining its two slots. An assignment of keys to slots is an orientation of that graph in which every edge points at the slot its key occupies, and it is valid exactly when no two edges point at the same vertex — that is, when every vertex has in-degree at most one.

A graph has such an orientation if and only if no connected component has more edges than vertices. A component with $k$ vertices and $k$ edges has exactly one cycle and can be oriented; a component with $k+1$ edges cannot, because $k$ vertices cannot hold $k+1$ keys.

So the question is when a random graph on $2m$ vertices with $n$ edges has a component with more edges than vertices — and that is a classical threshold. It happens with probability approaching zero below $n = m$ and approaching one above it, which in this structure’s units is a load of one half. The displacement chain fails to terminate exactly when the graph the keys drew has a component too dense to orient.

That is why the transition is sharp: the emergence of a dense component in a random graph is itself a sharp event, and the sharpening with size is the same finite-size effect that appears in every random-graph threshold.

The graph picture also explains a detail of the implementation that would otherwise look arbitrary: the displacement limit. A chain that has gone round more than a few times is, with high probability, inside a component that cannot be oriented — so it will never terminate, and continuing is pointless. The limit is a heuristic for detecting a structural impossibility, it is usually set at a small multiple of $\log$ of the table size, and it is one of the tuning constants the threshold somebody chose is about: a number in a real source file, not derived from the analysis, deciding behaviour the analysis does not mention.

What the construction costs when it succeeds #

The failure rate is one column and the work is another, and the second rises smoothly where the first does not.

At a load of 0.4 on a table of a thousand slots, inserting 819 keys performs 359 displacements — 0.44 per key — and the longest single chain is eleven. At 0.2 the average is 19 displacements over the whole construction; at 0.6 it is 299. So the work per insertion grows steadily through the region where the failure probability is still zero, and a system watching only the average displacement count would see a slow degradation and no warning at all of the cliff ahead.

That is worth stating as a general shape because it recurs. The quantity that degrades gracefully and the quantity that fails are different quantities, and watching the first says nothing whatever about the second. The dashed line on the plates is the average displacement count and it is drawn precisely so the two can be compared: it rises by a factor of fifteen across the sweep, monotonically, through a region in which the failure rate goes from zero to one.

What a failed construction means for the caller #

There is a practical question the plates do not answer directly and it is the one an implementer asks first: what does the caller see?

Not an error, in any well-behaved implementation. The table draws two fresh hash functions and reinserts everything, which takes time proportional to the number of keys and succeeds with the same probability as before — so the expected number of restarts is a small constant below the threshold, and the amortised cost of an insertion stays constant. The failure is invisible from outside, and its cost is a latency spike rather than an exception.

That has two consequences worth separating. It makes the technique safe below the threshold: a caller sees constant expected insertion and exactly two probes on every lookup, which is the advertised behaviour. And it makes the technique unusable above it, in a way that is worse than merely slow: past the threshold nearly every construction fails, so the restart loop does not terminate in any useful sense, and the structure has no graceful degradation to fall back on.

So the load factor is not a performance knob. It is a correctness boundary with a probabilistic edge, and a system that lets its table drift past it does not get slower, it stops working. The usual repair is the same one every dynamic array uses — grow when the load crosses a threshold well below the dangerous one — and choosing a growth factor is the essay about what that costs.

What the two probes are worth #

A worst case of two is a strange thing to want, and it is worth being concrete about who wants it.

A lookup that must fit in a fixed budget. A packet forwarder deciding where to send a frame has a few nanoseconds and no ability to take longer on an unlucky key. An expected constant with a long tail is unusable there; two reads, always, is exactly the shape needed.

A lookup on hardware without a loop. The same argument in silicon: two parallel reads and a comparison is a circuit, and a probe sequence of unbounded length is not.

And a structure whose reads are remote. The same argument the block that is not a block makes about dependent chains applies here in the algorithm’s favour: a cuckoo lookup’s two reads are independent, so they can be issued together, where a probe sequence’s reads are a chain. If a probe is a network round trip, the difference between “expected 1.5 probes” and “exactly 2 probes” is small, and the difference between either and “occasionally 20” is everything.

What none of those wants is the restart. So the technique is used where the key set is known in advance and built once — a routing table, a static dictionary, a compiled perfect-hash-adjacent structure — and much less where keys arrive continuously.

The load-factor cost is the other half. Half a slot per key means the table is twice the size of the data, against a chained table that runs comfortably at a load of one or more. The guarantee costs a factor of two in space, on top of the failure risk, and that is a large price for a bound.

Where this sits among the field’s other bargains #

Four structures in this field now trade differently against randomness and setting them beside each other is what the ladder is for.

A skip list (a structure made of coin flips) spends randomness per key and gets an expected search cost with a tail. Its shape is decided entirely by the coins and not at all by the data.

Two choices (the second choice) spends no randomness per key, improves a tail, and creates no guarantee.

A Bloom filter (a filter allowed to be wrong) gives up exactness in one direction and gets a fixed cost — four probes, always — with an error rate as the price.

Cuckoo hashing keeps exactness, gets a fixed cost, and puts the price into a construction that can fail.

Reading those four together, the pattern is that a fixed worst-case cost is available in this field only by giving something up that is not time: either correctness in one direction, or the guarantee that the structure can be built at all. That is not a theorem and it is a regularity worth noticing, and it is the reason the two structures with the tightest lookup bounds are the two with a failure mode rather than a tail.

What makes this the field’s clearest threshold #

This collection has met a number of thresholds and they are not all the same kind of object, so it is worth saying what distinguishes this one.

The threshold somebody chose is about numbers in real source files — a minrun of 32, an insertion cutoff of 16 — that decide behaviour and are not derived from any analysis. Those are chosen thresholds: somebody picked them, they could have been picked differently, and sweeping them shows a smooth curve with a shallow optimum somewhere.

This one is not chosen. Nobody set it, it cannot be moved by changing the implementation, and it is not the location of an optimum — it is the location of a discontinuity in what is possible. Below it a valid assignment of keys to slots exists with probability approaching one, above it with probability approaching zero, and the algorithm’s job is only to find one when it exists.

The distinction matters because the two behave differently under tuning. A chosen threshold rewards measurement: sweep it, find the flat region, pick the middle. A structural threshold punishes it: the flat region on either side tells nothing about where the edge is, and the only safe operating point is comfortably below it with a margin that has to be argued for rather than measured.

A parameter with a cliff in it is not tuned the way a parameter with a curve in it is, and knowing which kind is in hand is the first question rather than a refinement.

What is not measured here #

Only two hashes and one slot per bucket. With three hash functions the threshold rises to about 0.91, and with two hashes and four slots per bucket to about 0.98 — which is why every practical variant uses one or both, and why a real cuckoo filter runs at a load a chained table would be comfortable at. Nothing on this page measures either.

The restart is not costed. When a construction fails it is abandoned here. A real implementation draws new hashes and starts again, and the expected total cost including restarts is the number the amortised analysis is about. Measuring it would need many constructions at each load and is not on any plate.

And the keys are ordinary. Every key set here is drawn at random. A hash is a family, not a function shows what a key set chosen against a hash does, and the adversary who knows the seed shows what one chosen against a known seed does — and a cuckoo table’s failure mode under attack is that the construction fails every time, which is a denial of service rather than a slowdown.

Where this ladder goes next: the evidence a filter cannot remove #

The structure on this page has a sibling that gives up exactness and keeps the two-probe bound. Store, instead of the key, a short hash of it — a fingerprint — and the same displacement mechanism works with far less space, because a fingerprint is a byte and a key is a word.

That structure can do something the filter this field already measured cannot. A filter allowed to be wrong is a Bloom filter, and its one-sided error is bought by never removing evidence: a set bit may have been set by any of several keys, so clearing it on a deletion clears it for all of them, and a filter that can answer no about a key it holds is not a filter at all.

The measurement that follows is what deletion costs. Telling a Bloom filter to forget half its keys by clearing their bits loses most of the rest; a counter in each cell repairs that at four times the bits; and a fingerprint filter repairs it at twice, while acquiring a condition on the caller neither of the others has. Three structures, one operation, and three different prices — with the last one’s price being a precondition rather than a resource.