Cuckoo Hashing and the Guarantee of Two Probes

Every scheme described so far gives expected constant-time lookup. None gives a bound that holds for every operation. A single key can sit at the end of a linear-probing cluster of arbitrary length, and the lookup for it pays for the whole cluster. Cuckoo hashing is the design that changes this: it guarantees that a lookup examines at most two slots, unconditionally, with no probabilistic qualifier on the query path.

Two homes, no probe sequence

The table is an array of slots, and there are two independent hash functions h₁ and h₂. Every key has exactly two possible homes: slot h₁(k) and slot h₂(k). The invariant is that each key is stored in one of its two homes. There is no probe sequence beyond those two positions.

A lookup computes both homes, examines the two slots, and returns the key if either holds it. That is at most two memory accesses, and the bound holds regardless of load factor, insertion history, or adversarial input. This is the property that makes the structure interesting: the worst case is a constant, not a distribution.

The cost is that insertion is no longer a walk to a free slot. If both homes are occupied, the new key must displace one of the occupants. The displaced key then moves to its other home, displacing whatever is there, and the process continues. Each displaced key alternates between its two homes, so the chain of displacements is a walk in a graph whose vertices are keys and whose edges connect keys that share a home slot.

struct entry { const char *key; void *val; uint64_t h[2]; };

/* Insert e, whose two homes are e.h[0] and e.h[1]; start by trying home `which`. */
int cuckoo_insert(struct table *t, struct entry e, int which)
{
    for (int i = 0; i < MAX_KICKS; i++) {
        size_t slot = e.h[which] & t->mask;
        struct entry evicted = t->slot[slot];
        t->slot[slot] = e;                        /* place current, evict occupant */
        if (evicted.key == NULL)
            return 0;                             /* the chain ended in an empty slot */

        e = evicted;
        /* the evicted key sat at one of its homes; it must try the other one */
        which = ((evicted.h[0] & t->mask) == slot) ? 1 : 0;
    }
    return 1;                                     /* too many kicks: give up */
}

The loop bound is the mechanism’s safety valve. If the chain of displacements exceeds a fixed number of kicks, the table is assumed to contain a cycle, and the insertion is abandoned in favour of rehashing with new functions. Without the bound, a cycle would loop forever; with it, the failure is detected and repaired.

Why two homes are enough, and where the threshold sits

The load threshold at which cuckoo hashing stops working is a property of the graph, not of the hash functions’ quality. If every key is placed at one of two random homes, the placement problem is equivalent to orienting the edges of a random graph so that no vertex has more than one incoming edge. Such an orientation exists with high probability only while the average degree is below a threshold.

For the simplest version, with one key per slot and two choices, the threshold is a load factor of about 0.5 for the two-hash construction with a random hash family: below that, insertion almost always succeeds within a short chain; above it, cycles appear and the table needs rehashing, which may fail again immediately if the load is still above the threshold. A cuckoo table is therefore kept at α ≤ 0.5, roughly half the load a linear-probed table tolerates, which doubles its memory per key.

The threshold can be raised by increasing the number of slots per bucket. With two buckets of size d, each key has 2d possible homes and the orientation problem becomes one of placing up to d keys per vertex. The threshold rises with d, moving above 0.5 for buckets of two slots and approaching 1 as d grows, at the cost of examining 2d slots per lookup. The lookup bound stays constant for fixed d, which is the point: d is chosen to trade memory density against the constant.

A second way to raise the threshold is to add a small stash, a secondary structure holding a few keys that could not be placed. Lookup checks the two homes and then the stash, which is small enough to be searched quickly or held in a register-resident array. The stash absorbs exactly the keys that would otherwise trigger a rehash, so a table with a stash of a few dozen entries can run at a load factor well above the plain threshold. The worst-case lookup bound becomes two slots plus the stash size, which is still constant.

Rehashing, failure, and the possibility of a loop

Rehashing in a cuckoo table is different from rehashing elsewhere. Because the failure is caused by cycles in the placement graph, changing the table size alone may not help if the load factor is unchanged: the new graph has the same density and may have cycles too. Implementations therefore rehash with new hash functions, either by reseeding or by increasing the table size, and they must handle the case where the new placement also fails.

The standard approach is to double the table on failure, which halves the load factor and makes the new placement succeed with high probability. Repeated failure at successively larger sizes is possible in principle and vanishingly unlikely in practice, but an implementation must still terminate: after a bounded number of doublings, it can fall back to a structure without the two-probe guarantee.

There is a second, subtler failure mode. The displacement chain can be long even when it succeeds. An insertion may kick a key, which kicks another, and so on for hundreds of steps before finding an empty slot. The insertion cost is then linear in the chain length, and the amortized bound depends on the chain length being short on average. Near the threshold, chains lengthen sharply, which is why the load factor must be kept below it rather than at it.

The interaction between the two is what makes the analysis delicate. The expected insertion cost is constant while α is comfortably below the threshold, grows as the threshold is approached, and becomes unbounded at it. The lookup guarantee is unaffected by all of this, which is the asymmetry the design accepts: queries are worst-case constant, updates are amortized expected constant, and the memory is roughly double.

Why deletion cannot break another key’s placement

Deletion is a lookup followed by clearing the slot. Nothing else is required, because no other key depends on the deleted key’s position: every key is at one of its own two homes regardless of what its neighbours do. This is a genuine advantage over linear probing, where deletion requires repairing a chain.

The simplicity has one consequence worth stating: there is no ordering invariant between keys, so a freed slot needs no repair and cannot invalidate a neighbour. It is simply available, and the next insertion whose home is that slot will take it.

The absence of an ordering invariant is also what makes concurrent implementations tractable: two operations that touch different slots do not interfere, and an insertion’s displacement chain touches a bounded set of slots at each step. Lock-free cuckoo tables exist, and their correctness argument rests on the same two-home invariant, with the added requirement that a displaced key is never lost between the moment it is evicted and the moment it is reinserted.

What the guarantee costs

The two-probe bound is bought with memory and with update complexity. At α = 0.5 the table wastes half its slots, and the slot array must be sized to twice the key count. Against an open-addressed table at α = 0.75 that is 1.5 times the slot array, and against a chained table it is a larger array but no per-key node or chain pointer.

The update path is where the design is most fragile. Insertion may fail, may loop, may require a full rehash, and may need new hash functions. Any implementation must handle all of these, and the rehash itself must be able to fail without corrupting the table. That is a substantial amount of code for a structure whose query path is two array reads.

The payoff is predictability. In a system where a lookup must complete within a fixed budget, a two-probe bound is worth more than a better average, because the average was never the constraint. The same reasoning drives the bounded-probe designs built on SIMD comparison, where the control bytes of a whole group are tested at once; that layout is described in SwissTable control bytes. Both accept extra memory and more elaborate insertion to convert an expected bound into a guaranteed one.