Search tools and guides ⌘K
III · Hashing & lookup

Cuckoo hashing

Two slots, no chains.

2001 · Rasmus Pagh & Flemming Rodler · Aarhus
The story

Two Danish researchers solved the worst-case-O(1) lookup problem. Each key has two possible homes; on collision, the new key kicks the old one out (the "cuckoo") to its other home. Looks impossible until you read the analysis — when load factor is below 50%, infinite chains are vanishingly unlikely.

How it works

Two hash tables, two hash functions. Lookup checks both. Insert: place at h1; if occupied, evict that key to its h2; if that's occupied, evict it to its h1; continue until empty slot or rehash.

Where it lives

Cuckoo filter (a Bloom filter alternative). Some routers' MAC tables. Memcached extensions. CockroachDB transaction status records.

The key insight

Cuckoo hashing's worst-case-O(1) lookup is rare and valuable — most hash tables only guarantee O(1) on average. Used where adversarial inputs make average-case bounds insufficient.

More in Hashing & lookup
Hash table O(1), almost always. Robin Hood hashing Steal from the rich, give to the poor. Consistent hashing Hashing that survives node changes. Perfect hashing Zero collisions, by design.
Across the cabinet
IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it.
← All data structures