Cuckoo Hashing

Cuckoo Hashing is an open-addressed dictionary data structure and collision-resolution algorithm in computation and algorithms that provides worst-case O(1) constant-time lookup and deletion together with amortized expected O(1) insertion. Introduced by Danish computer scientists Rasmus Pagh and Flemming Friche Rodler in 2001, the scheme takes its name from the brood-parasitic behavior of the European cuckoo bird (Cuculus canorus), whose newly hatched chick pushes existing host eggs out of the nest to claim the slot for itself.

In classical hash table designs such as separate chaining or linear probing, lookup time is O(1) only in expectation; in the worst case, hash collisions can cluster keys into chains or probe sequences of length Θ(log n / log log n) (or Θ(log n) under linear probing), creating tail-latency spikes and algorithmic complexity denial-of-service vulnerabilities. Cuckoo hashing eliminates variable-length probe sequences by assigning every key x at most two candidate memory locations T₁[h₁(x)] and T₂[h₂(x)]. If both candidate slots are occupied during insertion, the new key evicts one of the incumbent keys, which then relocates to its own alternative nest along an augmenting path in the bipartite cuckoo graph—a paradigm that also powers space-efficient Cuckoo Filters as deletion-capable alternatives to the Bloom filter.

Dual Hash Tables and Branch-Free Constant-Time Lookup

In its canonical two-table formulation, a cuckoo hash table consists of two arrays T₁[0 .. r − 1] and T₂[0 .. r − 1] of total capacity m = 2r slots, paired with two independent hash functions h₁, h₂ : U → {0, 1, ..., r − 1}. The fundamental structural invariant of cuckoo hashing is that every stored key x ∈ S resides at either T₁[h₁(x)] or T₂[h₂(x)]—and nowhere else:

• Lookup(x): Inspect T₁[h₁(x)] and T₂[h₂(x)]:

Because the two memory addresses h₁(x) and h₂(x) depend only on x and are independent of one another, modern superscalar CPUs issue both memory loads in parallel in a single pipeline stage, achieving deterministic worst-case O(1) lookup in at most 2 cache line accesses.

• Delete(x): Check the same two slots T₁[h₁(x)] and T₂[h₂(x)]; if either contains x, clear that slot to empty (⊥) in worst-case O(1) time without needing tombstones.

The Cuckoo Eviction Loop and Cycle Detection

To Insert(x), the algorithm first checks whether x is already present. If not, it attempts to place x into T₁[h₁(x)]:

1. If T₁[h₁(x)] is empty (⊥), write T₁[h₁(x)] ← x and terminate.
2. If T₁[h₁(x)] is already occupied by an incumbent key y, evict y by setting T₁[h₁(x)] ← x, and attempt to insert the displaced key y into its alternative location T₂[h₂(y)] in the second table.
3. If T₂[h₂(y)] is occupied by a third key z, evict z (T₂[h₂(y)] ← y) and move z to T₁[h₁(z)], alternating between T₁ and T₂ until either an empty slot is reached or the number of displacements reaches a logarithmic cap MaxLoop = ⌈3 log_1+ε r⌉.

If the eviction sequence reaches MaxLoop without finding a vacant slot, the table has encountered a closed cycle chain; the algorithm picks a fresh pair of hash functions (h₁′, h₂′) from a universal hash family and rehashes the table (or places the displaced item into a tiny constant-sized stash).

Random Bipartite Graph Theory and the α = 50% Threshold

The behavior of cuckoo hashing is governed by the topology of the random bipartite cuckoo graph G = (V₁, V₂, E), where V₁ and V₂ represent the r buckets of T₁ and T₂ (|V₁| = |V₂| = r) and each stored key x ∈ S induces an undirected edge e(x) = (h₁(x), h₂(x)) connecting its two candidate buckets. A set of n keys can be placed without collision if and only if every connected component of G has at most as many edges as vertices—that is, every connected component is either a tree or unicyclic (containing at most one cycle).

When n < r (so the overall load factor α = n / (2r) = (1 / (2(1 + ε))) < 0.50), random graph theory (Erdős–Rényi phase transition) establishes that with high probability 1 − O(1/n) every connected component of G is subcritical and has size O(log n), expected insertion takes O(1 + 1/ε) constant time, and the probability that an insertion triggers a full rehash is O(1/n²). Conversely, once n > r (load factor α > 50%), a giant bicyclic component emerges with high probability and 2-choice cuckoo hashing with 1 item per bucket fails.

d-ary Cuckoo Hashing, Bucketized Cuckoo Hashing, and Kirsch–Mitzenmacher Stash

To increase space utilization from 50% to 90%–98% while retaining worst-case O(1) lookup, three structural enhancements are employed in practice:

1. d-ary Cuckoo Hashing (Fotakis et al., 2005): Uses d ≥ 3 hash functions (h₁, ..., h_d) per key. Increasing from d = 2 to d = 3 raises the phase-transition load threshold from 50.0% to 91.79%, and d = 4 reaches 97.68%.
2. Bucketized (b-Slot) Cuckoo Hashing (Dietzfelbinger & Weidling, 2007): Keeps d = 2 hash functions (preserving 2 parallel memory accesses), but widens each bucket into a cache-line-aligned slot array holding b = 4 or b = 8 keys. With d = 2 and b = 4 keys per bucket, the maximum load factor jumps from 50% to 95.04%; with b = 8, it reaches 98.52%.
3. Cuckoo Stash (Kirsch, Mitzenmacher, & Wieder, 2009): Adding a tiny auxiliary array (a stash) of just s = 3 or 4 elements checked on every lookup reduces the rehash failure probability from O(1/n) to O(1/n^s+1) = O(1/n⁵), eliminating rehashes in practice.

In 2014, Bin Fan, Dave Andersen, Michael Kaminsky, and Michael Mitzenmacher introduced the Cuckoo Filter, an approximate set-membership structure that stores compact f-bit fingerprints τ = fingerprint(x) inside a bucketized (d = 2, b = 4) cuckoo table. Because the full key x is not stored in the table, standard eviction h₂(x) would appear impossible during a relocation; Cuckoo Filters solve this via partial-key cuckoo hashing, defining the alternate bucket index via involutory bitwise XOR:

This XOR symmetry allows an evicted fingerprint to compute its twin bucket index i₂ from its current bucket index i₁ and its own fingerprint alone, providing O(1) deletions, two-cache-line lookups, and lower bits-per-item space overhead than a standard Bloom filter for false-positive rates ε < 3%. In networking hardware and software routers (such as Intel DPDK's rte-hash library and P4 programmable switches), bucketized cuckoo hashing maps IPv4/IPv6 flows in deterministic clock cycles alongside consistent hashing load balancers and Count–Min sketch telemetry monitors.

How can a Cuckoo Filter relocate an evicted item without storing the original key?

In partial-key cuckoo hashing, the two candidate buckets i₁ and i₂ for key x are linked by the reversible XOR identity i₂ = i₁ ⊕ h(τ), where τ is the short f-bit fingerprint stored in the bucket. Because a ⊕ b ⊕ b = a, whether the fingerprint currently sits in bucket i₁ or bucket i₂, XORing the current bucket index with h(τ) always yields the other candidate bucket index without needing the original key x.

Why does standard 2-choice cuckoo hashing fail above a 50% load factor, whereas 2-choice bucketized cuckoo hashing with 4 slots per bucket reaches 95%?

With b = 1 slot per bucket, a connected component of k buckets overflows as soon as it receives k + 1 keys (a unicyclic threshold equivalent to the Erdős–Rényi random graph transition at average degree 1, or α = 0.50). With b = 4 slots per bucket, a connected component of k buckets can absorb up to 4k keys before overflowing (corresponding to the 4-core hypergraph orientability threshold), raising the phase transition to α ≈ 0.9504 while still fitting each 4-slot bucket inside a single 64-byte CPU cache line.

Does cuckoo hashing require cryptographic hash functions to achieve O(1) lookup guarantees?

No. While cryptographic hash function families work, Pagh and Rodler proved that O(log n)-wise independent hash families suffice theoretically, and in practice simple tabulation hashing (Pătrașcu & Thorup, 2012)—which splits a 64-bit key into eight 8-bit characters and XORs eight 256-entry lookup tables kept in L1 cache—provides the theoretical cuckoo stash bounds at speeds comparable to a single 64-bit multiplication.

1. Pagh, R., & Rodler, F. F. (2001). "Cuckoo hashing." Proceedings of the 9th Annual European Symposium on Algorithms (ESA 2001), LNCS Vol. 2161, 121–133 (Journal version in Journal of Algorithms, 51(2), 122–144, 2004). https://doi.org/10.1016/j.jalgor.2003.12.002
2. Fotakis, D., Pagh, R., Sanders, P., & Spirakis, P. (2005). "Space efficient hash tables with worst case constant access time." Theory of Computing Systems, 38(2), 229–248. https://doi.org/10.1007/s00224-004-1195-x
3. Kirsch, A., Mitzenmacher, M., & Wieder, U. (2009). "More robust hashing: Cuckoo hashing with a stash." SIAM Journal on Computing, 39(4), 1543–1561. https://doi.org/10.1137/080728743
4. Pătrașcu, M., & Thorup, M. (2012). "The power of simple tabulation hashing." Journal of the ACM, 59(3), 14:1–14:50. https://doi.org/10.1145/2220357.2220361
5. Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). "Cuckoo Filter: Practically better than Bloom." Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT '14), 75–88. https://doi.org/10.1145/2674005.2674994