Cuckoo Hashing

Hash tables are everywhere: behind dictionaries in Python, maps in Java, and the indices that make databases fast. The idea is simple — hash a key to a slot, read or write in one step. $O(1)$, constant time.

The problem is collisions. When two keys hash to the same slot something must give. Standard solutions — chaining with linked lists, or probing nearby slots — degrade to $O(n)$ in the worst case or at least add unpredictability under heavy load.

In 2001, Rasmus Pagh and Flemming Friche Rodler published a scheme that trades that uncertainty away entirely. The idea was named cuckoo hashing after the bird that lays its egg in another bird's nest and ejects the existing occupant.

The rule is elegant: every key has two possible slots (one per hash function). Insertion tries the first slot. If it's taken, the resident is evicted to its own alternate slot — which may itself evict another occupant — and so on, in a chain. The result: lookup is always worst-case $O(1)$, because a key can only ever be in one of two fixed positions.

The demo below shows two hash tables of size 7. Every key hashes to one slot in Table A and one in Table B. Insert a key and watch the eviction chain: if your slot is occupied the resident hops to its alternate home, potentially triggering further hops.

<p class="hint">{{hint}}</p>
<div class="tables-wrap">
  <div class="tbl-block">
    <div class="tbl-label">{{table_a}}</div>
    <div id="tableA" class="tbl"></div>
  </div>
  <div class="tbl-block">
    <div class="tbl-label">{{table_b}}</div>
    <div id="tableB" class="tbl"></div>
  </div>
</div>
<div class="controls">
  <input id="keyInput" type="text" placeholder="{{placeholder}}" maxlength="8" />
  <button id="insertBtn" type="button">{{btn_insert}}</button>
  <button id="lookupBtn" type="button" class="ghost">{{btn_lookup}}</button>
  <button id="deleteBtn" type="button" class="ghost">{{btn_delete}}</button>
  <button id="resetBtn" type="button" class="ghost danger">{{btn_clear}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.tables-wrap { display: flex; gap: 1.4rem; margin-bottom: .8rem; }
.tbl-block { flex: 1; min-width: 0; }
.tbl-label { font-size: .75rem; font-weight: 700; letter-spacing: .06em; color: #5a7088; text-transform: uppercase; margin-bottom: .3rem; }
.tbl { display: flex; flex-direction: column; gap: 3px; }
.slot { display: flex; align-items: center; gap: .5rem; }
.slot-idx { font: 600 11px ui-monospace, monospace; color: #888; width: 16px; text-align: right; flex-shrink: 0; }
.slot-cell { flex: 1; min-width: 0; height: 34px; border-radius: 6px; border: 1px solid #cdd9e3;
             display: flex; align-items: center; padding: 0 .6rem;
             font: 600 13px ui-monospace, monospace; transition: background .25s, border-color .25s; }
.slot-cell.empty { background: #f2f5f8; color: #aaa; }
.slot-cell.filled { background: #dbeafe; border-color: #93c5fd; color: #1e40af; }
.slot-cell.highlight { background: #fef08a; border-color: #ca8a04; color: #92400e; }
.slot-cell.found { background: #bbf7d0; border-color: #4ade80; color: #065f46; }
.slot-cell.evicted { background: #fee2e2; border-color: #f87171; color: #991b1b; animation: hop .3s ease; }
@keyframes hop { 0%{transform:translateX(-6px);opacity:.5} 100%{transform:translateX(0);opacity:1} }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; align-items: center; }
#keyInput { font: 14px ui-monospace, monospace; padding: .4rem .6rem; border: 1px solid #cdd9e3;
            border-radius: 6px; width: 110px; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border-radius: 6px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
button.danger { border-color: #c92f3c; color: #c92f3c; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #065f46; }
.status.bad { color: #c92f3c; }
.status.info { color: #1e40af; }
.log { font: 12px ui-monospace, monospace; color: #555; max-height: 90px; overflow-y: auto;
       border-top: 1px solid #e2e8f0; padding-top: .3rem; }
.log div { margin-bottom: 2px; }

// Code not found

Notice that lookup is always two checks: slot h1(key) in Table A, then slot h2(key) in Table B. No matter how many evictions happened during insertion, a key is always in one of those two fixed positions — worst-case $O(1)$ is guaranteed. If an eviction cycle is detected the tables are rebuilt with new hash functions (a rehash).

Let's be precise about what cuckoo hashing actually guarantees:

• Lookup: worst-case $O(1)$. A key is always in h1(key) in Table A or h2(key) in Table B. Two memory accesses, never more, regardless of table occupancy or key distribution.
• Deletion: worst-case $O(1)$. Check both slots, remove. No tombstones, no cascading cleanup.
• Insertion: $O(1)$ amortized with high probability. The eviction chain is usually short. Pagh and Rodler proved that at load factor below 50% per table, the expected chain length is $O(1)$. A cycle can occur (with exponentially small probability), which triggers a full rehash with new hash functions — this is the rare expensive case.
• Space: 2n slots for n keys (one slot per key on average across two tables), so load factor ≈ 50%.

Why does it work? Model the two tables as a bipartite graph: keys are edges between their two candidate slots. An insertion succeeds if and only if the connected component containing the new key's slots is acyclic — a forest admits a valid assignment, a cycle does not. When the graph is sparse (load factor < 50%), cycles are rare.

This is in contrast to chaining (worst-case $O(n)$) or open addressing with probing (worst-case $O(n)$ and cache behaviour degrades). See also pattern matching for another domain where worst-case guarantees are crucial, and sorting lower bounds for similar complexity arguments.

The guarantee "at most two lookups, always" matters enormously in latency-sensitive systems:

• Network routers and switches: packet forwarding tables must look up IP addresses at line rate — tens of millions of packets per second. Hardware implementations of cuckoo hashing (often with more than two tables for higher load) give deterministic latency.
• Databases and key-value stores: hash indexes in systems like Redis and PostgreSQL benefit from predictable lookup time. Variants of cuckoo hashing appear in RocksDB's block cache and in DPDK's hash library.
• Filters and sets: Cuckoo filters (a 2014 extension by Fan et al.) adapt the idea to approximate membership testing, matching Bloom filter space efficiency while supporting deletions — something Bloom filters cannot do.
• Hardware CAMs: Content-Addressable Memory used in network ASICs uses cuckoo-like multi-way placement to maximise utilisation.

The core insight — give each element multiple candidate positions and let them negotiate — also appears in max matching on bipartite graphs, which is precisely the theoretical model underlying cuckoo hashing's analysis.

Cuckoo hashing shows that the right framing turns a headache into an elegant solution. Collisions are not an obstacle to work around — they are an eviction game to play. Give every key two homes, let residents negotiate, and the chaos resolves itself into a structure where lookup is always two steps, provably.

The price is modest: a 50% load cap and occasional rehashes. The payoff — a hash table with a genuine worst-case guarantee — is rare enough in algorithm design to be remarkable. The next time you see a network switch forward packets at nanosecond speed, there is a good chance a cuckoo is quietly nesting behind it.