Cuckoo Hashing

How cuckoo hashing works

Cuckoo hashing is named after the European cuckoo, which lays eggs in other birds' nests and shoves the rightful chicks out. The data structure does the same: when a new key wants a slot already occupied, it kicks the incumbent out and the incumbent has to find another home.

The setup uses two arrays (or one array conceptually split in two) and two independent hash functions, h1 and h2. A key k can live only at h1(k) or h2(k) — never anywhere else. To look up k, check both slots; if it's not in either, it's not in the table. That's why lookups are worst-case O(1) — you never probe a chain.

Insertion is more interesting:

1. Place key k at h1(k). If empty, done.
2. If occupied by some k', evict k' and put k in its place.
3. k' is now homeless — move it to its other hash slot (h2(k') if it was at h1(k'), else h1(k')).
4. If that slot is also occupied, repeat the eviction with that key.
5. If the eviction chain exceeds a fixed budget (typically log n), give up and rehash with new h1, h2.

Most of the time the chain ends in one or two evictions. The pathological case is a cycle — three keys a, b, c whose two-slot pairs form a closed loop in the bipartite graph of (slot, key). The algorithm detects cycles by hitting the eviction budget and triggers a full rehash.

When to use cuckoo hashing

• Hard real-time systems where any tail-latency spike is a bug. A high-frequency-trading order book or a network switch's flow table cannot tolerate the 100-slot probe sequences that linear probing produces near full load.
• Read-heavy workloads where lookups vastly outnumber inserts. Cuckoo's two-read worst case crushes everything else; the rare rehash on insert is amortized away.
• Memory-constrained probabilistic sets where you want a Bloom-filter alternative that supports deletion and gives lower false-positive rates — that's the cuckoo filter (an industrial application of cuckoo hashing).
• Cache-sensitive embedded code where you want predictable two-cache-line access per lookup, which simplifies CPU prefetching.

Cuckoo vs other open-addressing schemes

	Cuckoo (2-way)	Linear probing	Robin Hood	Hopscotch
Lookup (worst)	O(1) — 2 reads	O(n)	O(log n) avg, O(n) worst	O(H), H ≈ 32
Lookup (avg, 90% load)	~1.5 reads	~5 reads	~2 reads	~2 reads
Insert (worst)	O(n) on rehash	O(n) on cluster	O(n) on shift	O(n) on displacement
Max load factor	~50% (2-way), 97% (4-ary)	~70% before degradation	~90%	~90%
Cache locality	Poor (2 random reads)	Excellent (linear)	Excellent (linear)	Good (neighborhood)
Supports deletion	Trivial — clear slot	Tombstones required	Backward shift	Trivial in neighborhood
Tail-latency predictability	Excellent	Poor	Moderate	Good (bounded)

The headline number: at 90% load, linear probing averages roughly 5 probes per lookup (and worst case is in the hundreds), while cuckoo averages ~1.5 probes and worst case is exactly 2. That's the tradeoff — you give up cache locality in exchange for tight worst-case guarantees.

JavaScript implementation

This implementation uses two tables and a fixed eviction budget. On budget exhaustion, it rehashes (in production you'd swap in fresh hash functions and re-insert).

class CuckooHash {
  constructor(capacity = 16) {
    this.cap = capacity;
    this.t1 = new Array(capacity).fill(null);
    this.t2 = new Array(capacity).fill(null);
    this.size = 0;
    this.maxLoop = Math.ceil(Math.log2(capacity)) * 4;
  }

  // Two independent hashes — in practice, use SipHash, MurmurHash, etc.
  h1(k) { return (k * 2654435761) % this.cap; }
  h2(k) { return ((k * 40503) ^ 0x9e3779b1) % this.cap; }

  lookup(k) {
    if (this.t1[this.h1(k)] === k) return true;
    if (this.t2[this.h2(k)] === k) return true;
    return false;  // worst case: exactly 2 reads
  }

  insert(k) {
    if (this.lookup(k)) return;
    let cur = k;
    let useTable1 = true;
    for (let i = 0; i < this.maxLoop; i++) {
      const idx = useTable1 ? this.h1(cur) : this.h2(cur);
      const tbl = useTable1 ? this.t1 : this.t2;
      if (tbl[idx] === null) {
        tbl[idx] = cur;
        this.size++;
        return;
      }
      // Evict the incumbent and continue the chain.
      [tbl[idx], cur] = [cur, tbl[idx]];
      useTable1 = !useTable1;
    }
    // Cycle or near-full table — rehash everything.
    this.rehash(cur);
  }

  rehash(stranded) {
    const all = [stranded, ...this.t1.filter(x => x !== null),
                            ...this.t2.filter(x => x !== null)];
    this.cap *= 2;
    this.t1 = new Array(this.cap).fill(null);
    this.t2 = new Array(this.cap).fill(null);
    this.size = 0;
    this.maxLoop = Math.ceil(Math.log2(this.cap)) * 4;
    for (const k of all) this.insert(k);
  }

  delete(k) {
    if (this.t1[this.h1(k)] === k) { this.t1[this.h1(k)] = null; this.size--; return true; }
    if (this.t2[this.h2(k)] === k) { this.t2[this.h2(k)] = null; this.size--; return true; }
    return false;
  }
}

Notice that delete is trivial — clear the slot. Linear-probing tables can't do that without tombstones, because clearing a middle slot would orphan everything past it in the probe sequence.

Python implementation

import math

class CuckooHash:
    def __init__(self, capacity=16):
        self.cap = capacity
        self.t1 = [None] * capacity
        self.t2 = [None] * capacity
        self.size = 0
        self.max_loop = math.ceil(math.log2(capacity)) * 4

    def h1(self, k):
        return (hash(k) * 2654435761) % self.cap

    def h2(self, k):
        return ((hash(k) * 40503) ^ 0x9e3779b1) % self.cap

    def lookup(self, k):
        return self.t1[self.h1(k)] == k or self.t2[self.h2(k)] == k

    def insert(self, k):
        if self.lookup(k):
            return
        cur, use_t1 = k, True
        for _ in range(self.max_loop):
            idx = self.h1(cur) if use_t1 else self.h2(cur)
            tbl = self.t1 if use_t1 else self.t2
            if tbl[idx] is None:
                tbl[idx] = cur
                self.size += 1
                return
            tbl[idx], cur = cur, tbl[idx]
            use_t1 = not use_t1
        self._rehash(cur)

    def _rehash(self, stranded):
        all_keys = [stranded] + [x for x in self.t1 if x is not None] \
                              + [x for x in self.t2 if x is not None]
        self.cap *= 2
        self.t1 = [None] * self.cap
        self.t2 = [None] * self.cap
        self.size = 0
        self.max_loop = math.ceil(math.log2(self.cap)) * 4
        for k in all_keys:
            self.insert(k)

    def delete(self, k):
        if self.t1[self.h1(k)] == k:
            self.t1[self.h1(k)] = None
            self.size -= 1
            return True
        if self.t2[self.h2(k)] == k:
            self.t2[self.h2(k)] = None
            self.size -= 1
            return True
        return False

For production use you'd replace the multiplicative hashes with cryptographically-mixed functions like SipHash; the toy hashes above can collide pathologically on adversarial inputs and trigger non-stop rehashes — a denial-of-service vector that has bitten real systems.

Variants

• d-ary cuckoo. Use d hash functions instead of 2. With d = 4, peak load factor jumps from ~50% to ~97%, but lookups now read 4 slots worst case instead of 2.
• Blocked cuckoo (bucketized cuckoo). Each "slot" holds a small bucket of 4 or 8 keys. Lookups scan the bucket linearly, which is one cache miss instead of one read. With 2 hashes × 4-slot buckets, peak load reaches 99%.
• Stash. A tiny side array (typically 4 entries) where keys land when the eviction chain hits the budget. Lookups check the stash on miss. A constant-size stash lets the table tolerate occasional bad runs without a full rehash.
• Cuckoo filter. Replace stored keys with 8–16 bit fingerprints; you can no longer reconstruct the key, only test membership. Beats Bloom filters at false-positive rates below ~3% and supports deletion.
• MemC3 / Horton tables. Practical engineering refinements layered on cuckoo to fit modern memory hierarchies — used in Memcached and high-performance KV stores.

Common bugs and edge cases

• Eviction cycles. Three keys whose two-slot homes form a closed loop in the bipartite graph cannot all be placed. Detect by hitting the maxLoop budget. Don't let inserts run forever.
• Choosing maxLoop too small. Triggers spurious rehashes — pick at least 4 · ⌈log₂ n⌉. Too large wastes time before giving up on a real cycle.
• Identical hash functions. If h1 and h2 happen to collide on the same indices for a workload, the table degenerates into a 1-way table and breaks instantly. Use independent hash families (e.g., tabulation hashing) and re-seed on rehash.
• Forgetting which table held the evicted key. When you evict, the next hash to try is the displaced key's other table, not the same one. Toggling a useTable1 flag is the standard approach.
• Adversarial keys forcing unbounded rehashes. If an attacker can pick keys (HTTP headers, URL params), they can drive your table into rehash loops. Mitigation: keyed hashes (SipHash with a per-process secret key).
• Load-factor brittleness. Vanilla 2-way cuckoo gets exponentially worse beyond 50% load. Watch size / cap and resize at 0.45, not 0.75 like a linear-probing table.

Historical note

Cuckoo hashing was introduced by Pagh and Rodler in 2001. Earlier "two-choice" load-balancing results — Azar, Broder, Karlin, and Upfal's 1994 paper showing that picking the lesser-loaded of two random bins exponentially reduces maximum load — laid the theoretical groundwork. Cuckoo hashing is the data-structure realization of the same idea: two random homes per item slashes the worst-case probe length from O(log n / log log n) to O(1).