Cuckoo Hashing, in depth: two-probe lookups, the cuckoo graph, bucketised load limits, stashes and a hash-correlation trap

How it works

Use two tables, T0 and T1, each with m slots, and two independent hash functions. Key x may live only at T0[h1(x)] or T1[h2(x)].

• Lookup checks those two slots. Two reads, no loop, no chain.
• Delete clears whichever slot holds the key. Unlike linear probing, there are no tombstones, because no other key's search path runs through that slot.
• Insert places x in T0[h1(x)]. If that slot held a key y, y is kicked out and moves to its slot in the other table, possibly kicking out z, and so on, like a cuckoo chick pushing eggs out of a nest. The chain ends when a key lands in an empty slot. If it runs longer than a limit, the insert gives up and the table is rebuilt with new hash functions or more space.

The figure traces six insertions with hand-picked hash values. Inserting B kicks A from T0[0] to T1[2]. Inserting D kicks C from T0[1] to T1[0]. Inserting E kicks B from T0[0] to T1[4], and inserting F kicks D from T0[1] to T1[3]. Each eviction is one step here because the other slot happened to be free. At higher load, chains get longer.

A complete implementation

The implementation below is complete and tested. It inserts 1,000 keys, reads all of them back and deletes one. Hashing uses multiply-shift: multiply the key's 64-bit hash by a random odd constant and keep the top bits. Each table gets its own constant. Why the top bits matter is covered under the hash-function trap below.

import random

MASK = (1 << 64) - 1

class CuckooTable:
    def __init__(self, bits=3, max_kicks=32, seed=1):
        self.bits, self.m = bits, 1 << bits          # slots per table
        self.T = [[None] * self.m, [None] * self.m]
        self.max_kicks, self.seed, self.n = max_kicks, seed, 0
        rng = random.Random(seed)
        self.mul = (rng.getrandbits(64) | 1, rng.getrandbits(64) | 1)

    def _h(self, i, key):                            # top bits of the product
        return ((self.mul[i] * (hash(key) & MASK)) & MASK) >> (64 - self.bits)

    def get(self, key):
        for i in (0, 1):                             # at most two probes
            e = self.T[i][self._h(i, key)]
            if e is not None and e[0] == key:
                return e[1]
        raise KeyError(key)

    def delete(self, key):
        for i in (0, 1):
            p = self._h(i, key)
            e = self.T[i][p]
            if e is not None and e[0] == key:
                self.T[i][p] = None                  # no tombstone needed
                self.n -= 1
                return
        raise KeyError(key)

    def put(self, key, value):
        for i in (0, 1):                             # overwrite if present
            p = self._h(i, key)
            e = self.T[i][p]
            if e is not None and e[0] == key:
                self.T[i][p] = (key, value)
                return
        entry, i = (key, value), 0
        for _ in range(self.max_kicks):
            p = self._h(i, entry[0])
            entry, self.T[i][p] = self.T[i][p], entry   # place, pick up victim
            if entry is None:
                self.n += 1
                return
            i ^= 1                                   # victim goes to other table
        self._rehash(entry)

    def _rehash(self, pending):
        items = [e for t in self.T for e in t if e is not None] + [pending]
        grow = len(items) > 0.45 * 2 * self.m        # near the 50% wall: grow
        fresh = CuckooTable(self.bits + grow, self.max_kicks, self.seed + 1)
        for k, v in items:
            fresh.put(k, v)
        self.__dict__.update(fresh.__dict__)

Starting from two 8-slot tables, 1,000 inserts usually end in two 1,024-slot tables at 0.488 load, after seven growth rebuilds (8 to 1,024 is seven doublings) plus zero to two reseeds. Python randomises string hashes per process, so results vary by run. In one of nine runs an insert failed just past the 45% growth line, and the table doubled again to 0.244 load. Note that put checks for an existing key first. Without that check, re-inserting a key creates a duplicate in the other table, and get may return the stale copy.

Why inserts fail: the cuckoo graph

Why does insertion fail, and why near half full? Model the table as the cuckoo graph. Every slot is a vertex and every key is an edge joining its two candidate slots. A valid placement assigns each edge to one of its endpoints, with no vertex used twice. A connected component with v vertices can therefore hold at most v keys. A tree component has v - 1 edges, which fit. A component with exactly one cycle has v edges, which still fit. A component with more edges than vertices, meaning two or more cycles, cannot be placed at all, and the eviction loop wanders forever.

The smallest example: keys X, Y and Z all hash to (3, 1). Three edges join the same two vertices, so no placement exists. Random-graph theory explains the 50% wall. With n keys and 2m slots, components stay small and almost all have at most one cycle while n/2m is below 1/2. Above that, a giant component with many cycles appears. Below the threshold the expected insertion cost is constant, but some insert fails with probability on the order of 1/m, which is why a rebuild path is not optional.

The graph also explains BFS insertion. Instead of a random walk of evictions, search outward from the new key's slots for the nearest empty slot, then move keys along that path from the far end. The path is as short as possible, and the search finds no path exactly when the component is full.

Buckets and more choices: load limits measured

Fifty per cent occupancy is wasteful, so practical designs give each key more room. Bucketised cuckoo hashing keeps two hash functions but makes each position a bucket of b slots. d-ary cuckoo hashing gives each key d candidate positions. The asymptotic load thresholds from the literature are about 0.897 for two choices with b = 2, about 0.98 for b = 4, about 0.918 for d = 3 single-slot tables and about 0.977 for d = 4. The simulation below inserts random 64-bit keys into 32,768 slots, with random-walk eviction capped at 500 kicks, until the first failure. It reports min, mean and max over 10 runs.

First failures come in below the asymptotic thresholds, as expected at finite size with a kick limit. The practical lesson stands: two choices and four slots per bucket give about 95% usable load with at most two bucket reads per lookup. Four 8-byte entries, or four small tags plus pointers, fit in one 64-byte cache line, so a lookup costs about two cache misses. That is the layout used by MemC3 and libcuckoo, and by cuckoo filters, which store fingerprints instead of keys.

The hash-function trap

Cuckoo hashing assumes the two hash functions behave independently. Correlated functions break it, and the failure looks like a bug elsewhere. This page's first prototype derived both positions from Python's tuple hash of (seed, key) for two seeds. It rebuilt forever at about 30% load in two 16-slot tables. A second attempt used multiply-shift but took the low bits with % nb. The low k bits of a product depend only on the low k bits of the inputs, so h2 became a fixed permutation of h1. Two keys that collided in one table always collided in the other. The simulation then failed at a mean load of 0.051 for b = 1 and 0.363 for b = 4. Taking the high bits fixed both, giving the numbers in the table above.

Rules that follow: derive positions from the high bits of multiply-shift, or from two independently seeded strong hashes. Never derive h2 from h1 by a fixed arithmetic step. Test the first-failure load as part of your unit tests, because a correlated-hash bug shows up as a load ceiling far below theory. If keys come from untrusted users, use a keyed hash with a per-process secret, because an attacker who can predict both positions can build the three-keys-two-slots pattern on purpose.

Kick limits, stashes and rebuilds

The worst-case insert is the weak point, so production designs add three controls.

• Kick limit. Cap the eviction chain at a small multiple of log m and treat hitting the cap as "this component is probably over-full". Without a cap, an insert into a two-cycle component never returns.
• A stash. Kirsch, Mitzenmacher and Wieder (ESA 2008) showed that a tiny overflow area of a few entries, checked on every lookup, cuts the rebuild probability sharply: with a stash of s entries it falls from about 1/m to about 1/m^(s+1). Their simulations found that three or four entries were enough to see large gains. Lookups pay a small, constant extra check.
• A rebuild policy. Rebuild with a new seed when load is low, and grow when it is near the threshold, as _rehash does above. A rebuild is O(n) and blocks, so latency-sensitive systems rebuild incrementally, or size the table so rebuilds happen only at planned growth points.

Concurrent cuckoo tables

Cuckoo tables suit read-heavy concurrent workloads, because a lookup touches only two buckets. Two systems show how writes are handled. MemC3 (Fan, Andersen and Kaminsky, NSDI 2013) used a 4-way bucketised table with small key tags. Writers first find the full eviction path, then move keys backwards from the empty end. A key is therefore always present somewhere. Readers check version counters, kept in a small striped array indexed by key hash, and retry if a writer changed the counter during the read. libcuckoo (Li, Andersen, Kaminsky and Freedman, EuroSys 2014) added BFS path search, which gives shorter paths and less lock time, and fine-grained locking for multiple writers. Its open-source C++ library is the usual starting point if you need a concurrent cuckoo map rather than writing one.

Failure modes

• Infinite insert loop. No kick cap, or a cap with no rebuild path, means one bad key hangs the writer.
• Duplicate keys. Insert skipped the existing-key check, so two versions of a key live in both tables.
• Correlated hashes. A load ceiling far below theory, frequent rebuilds and "random" failures in tests.
• Rebuild latency spikes. A rebuild that copies millions of entries stalls requests. Pre-size the table, or rebuild incrementally in the background.
• Adversarial keys. Predictable hashes let an attacker force rebuild storms. Use keyed hashing.
• Forgetting the stash on lookup. Entries parked in the stash become invisible.

Trade-offs and when to use it

Pick cuckoo hashing when lookup tail latency matters more than insert throughput: lookup-dominated caches, packet classification and flow tables, hardware tables in network devices, and read-mostly concurrent maps. Pick a SIMD open-addressing table for general-purpose maps with mixed reads and writes, where one sequential probe beats two random cache misses. If you only need membership with a small false-positive rate, use a filter instead: a Bloom filter, a cuckoo filter or a quotient filter.

What to do next

1. Run the implementation above and print its rehash count as you insert past 45% load.
2. Change it to b = 4 buckets and confirm that the first-failure load rises to about 0.95.
3. Swap the hash for low bits (% m) and watch the load ceiling collapse. Then add a first-failure-load test to your own hash-table test suite.
4. Add a 4-entry stash and measure how often rebuilds happen at 0.9 load with b = 4.
5. Replace the random walk with BFS path search and compare average and worst eviction lengths.
6. If you need concurrency, benchmark libcuckoo against your current map with your real read and write ratio before writing your own.