Introduction

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)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)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)O(1), because a key can only ever be in one of two fixed positions.

Try It

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">Each key has <b>two possible slots</b> — one in Table A, one in Table B. Inserting a key may kick out the current occupant, which hops to its own alternate slot. <b>Lookup always checks exactly 2 positions.</b></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="Key (e.g. cat)" maxlength="8" />
  <button id="insertBtn" type="button">Insert</button>
  <button id="lookupBtn" type="button" class="ghost">Lookup</button>
  <button id="deleteBtn" type="button" class="ghost">Delete</button>
  <button id="resetBtn" type="button" class="ghost danger">Clear</button>
</div>
<div class="status" id="status">Enter a key and click Insert.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Cuckoo hashing with two tables of size SIZE.
// h1(key) => slot in tableA,  h2(key) => slot in tableB.
//
// Insertion algorithm:
//   1. Simulate the eviction chain WITHOUT modifying any table, tracking
//      visited (table,slot) pairs to detect cycles.
//   2. Only if no cycle, replay the chain and commit all writes.
//
// This guarantees the tables are never left in a corrupt state.
// Lookup: check A[h1(key)] and B[h2(key)] — exactly 2 accesses, O(1) worst-case.

const SIZE = 7;

function hash1(key) {
  let h = 0;
  for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) >>> 0;
  return h % SIZE;
}
function hash2(key) {
  let h = 5381;
  for (let i = 0; i < key.length; i++) h = ((h << 5) + h + key.charCodeAt(i)) >>> 0;
  return h % SIZE;
}

const tableA = new Array(SIZE).fill(null);
const tableB = new Array(SIZE).fill(null);

// Build the eviction chain as an array of {table, slot, key} moves.
// Returns {chain, cycle}. chain[i] = {table:'A'|'B', slot, displaced: key|null}
// If a cycle is detected, returns {chain:[], cycle:true}.
function buildChain(key) {
  const visited = new Set(); // "A:slot" | "B:slot"
  const chain = [];
  let current = key;
  let useTable = 'A';

  while (true) {
    const slot = useTable === 'A' ? hash1(current) : hash2(current);
    const visitKey = useTable + ':' + slot;
    if (visited.has(visitKey)) return { chain: [], cycle: true };
    visited.add(visitKey);

    const occupant = useTable === 'A' ? tableA[slot] : tableB[slot];
    chain.push({ table: useTable, slot, key: current, displaced: occupant });
    if (occupant === null) return { chain, cycle: false }; // found empty slot
    current = occupant;
    useTable = useTable === 'A' ? 'B' : 'A';
  }
}

function commitChain(chain) {
  chain.forEach(({ table, slot, key }) => {
    if (table === 'A') tableA[slot] = key;
    else tableB[slot] = key;
  });
}

let lastEvicted = { A: [], B: [] };
let lastFound = { A: [], B: [] };

function renderTables() {
  ['A', 'B'].forEach(t => {
    const tbl = document.getElementById('table' + t);
    const arr = t === 'A' ? tableA : tableB;
    const evicted = lastEvicted[t];
    const found = lastFound[t];
    tbl.innerHTML = '';
    arr.forEach((key, i) => {
      const row = document.createElement('div');
      row.className = 'slot';
      const idx = document.createElement('div');
      idx.className = 'slot-idx';
      idx.textContent = i;
      const cell = document.createElement('div');
      let cls = 'slot-cell';
      if (key === null) { cls += ' empty'; cell.textContent = '—'; }
      else {
        cls += ' filled';
        if (evicted.includes(i)) cls += ' evicted';
        else if (found.includes(i)) cls += ' found';
        cell.textContent = key;
      }
      cell.className = cls;
      row.appendChild(idx);
      row.appendChild(cell);
      tbl.appendChild(row);
    });
  });
}

function logMsg(msg) {
  const log = document.getElementById('log');
  const d = document.createElement('div');
  d.textContent = msg;
  log.prepend(d);
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg;
  s.className = 'status ' + (cls || '');
}

function insertKey(key) {
  if (!key) { setStatus('Enter a key first.', 'bad'); return; }
  if (tableA[hash1(key)] === key) {
    setStatus(fmt('"%key%" " already in Table A slot %hash1%.', { key: key, hash1: hash1(key) }), 'info');
    return;
  }
  if (tableB[hash2(key)] === key) {
    setStatus(fmt('"%key%" " already in Table B slot %hash2%.', { key: key, hash2: hash2(key) }), 'info');
    return;
  }

  const { chain, cycle } = buildChain(key);

  if (cycle) {
    setStatus(fmt('Cycle detected for ""%key%""! Tables unchanged — a rehash with new hash functions is needed.', { key: key }), 'bad');
    logMsg(fmt('⚠ Cycle: ""%key%"" could not be inserted (rehash required)', { key: key }));
    lastEvicted = { A: [], B: [] };
    lastFound = { A: [], B: [] };
    renderTables();
    return;
  }

  // Commit: no cycle detected, safe to write
  commitChain(chain);
  const evictions = chain.length - 1;
  const last = chain[chain.length - 1];
  const evA = chain.filter(m => m.table === 'A' && m.displaced !== null).map(m => m.slot);
  const evB = chain.filter(m => m.table === 'B' && m.displaced !== null).map(m => m.slot);
  lastEvicted = { A: evA, B: evB };
  lastFound = { A: last.table === 'A' ? [last.slot] : [], B: last.table === 'B' ? [last.slot] : [] };
  renderTables();

  const evStr = evictions > 0 ? " " + fmt('(after %evictions% eviction%v%)', { evictions: evictions, v: evictions > 1 ? 's' : '' }) : '';
  setStatus(fmt('Inserted ""%key%"" into Table %table%, slot %slot%%evStr%.', { key: key, table: last.table, slot: last.slot, evStr: evStr }), 'ok');
  logMsg(fmt('✓ Insert "%key%" → %table%[%slot%]%evStr%', { key: key, table: last.table, slot: last.slot, evStr: evStr }));
}

function lookupKey(key) {
  if (!key) { setStatus('Enter a key first.', 'bad'); return; }
  const sA = hash1(key), sB = hash2(key);
  lastEvicted = { A: [], B: [] };
  if (tableA[sA] === key) {
    lastFound = { A: [sA], B: [] };
    renderTables();
    setStatus(fmt('"%key%" " found in Table A, slot %sA%. (2 checks)', { key: key, sA: sA }), 'ok');
    logMsg(fmt('🔍 "%key%" found at A[%sA%] (checked A[%sA%] + B[%sB%])', { key: key, sA: sA, sB: sB }));
  } else if (tableB[sB] === key) {
    lastFound = { A: [], B: [sB] };
    renderTables();
    setStatus(fmt('"%key%" " found in Table B, slot %sB%. (2 checks)', { key: key, sB: sB }), 'ok');
    logMsg(fmt('🔍 "%key%" found at B[%sB%] (checked A[%sA%] + B[%sB%])', { key: key, sB: sB, sA: sA }));
  } else {
    lastFound = { A: [], B: [] };
    renderTables();
    setStatus(fmt('"%key%" " not found. Checked A[%sA%] and B[%sB%] — exactly 2 slots.', { key: key, sA: sA, sB: sB }), 'bad');
    logMsg(fmt('🔍 "%key%" not found (checked A[%sA%] + B[%sB%])', { key: key, sA: sA, sB: sB }));
  }
}

function deleteKey(key) {
  if (!key) { setStatus('Enter a key first.', 'bad'); return; }
  const sA = hash1(key), sB = hash2(key);
  lastEvicted = { A: [], B: [] };
  lastFound = { A: [], B: [] };
  if (tableA[sA] === key) {
    tableA[sA] = null;
    renderTables();
    setStatus(fmt('"%key%" " deleted from Table A, slot %sA%.', { key: key, sA: sA }), 'ok');
    logMsg(fmt('✗ Deleted "%key%" from A[%sA%]', { key: key, sA: sA }));
  } else if (tableB[sB] === key) {
    tableB[sB] = null;
    renderTables();
    setStatus(fmt('"%key%" " deleted from Table B, slot %sB%.', { key: key, sB: sB }), 'ok');
    logMsg(fmt('✗ Deleted "%key%" from B[%sB%]', { key: key, sB: sB }));
  } else {
    setStatus(fmt('"%key%" " not in table — nothing to delete.', { key: key }), 'bad');
    logMsg(fmt('✗ Delete "%key%" → not found', { key: key }));
    renderTables();
  }
}

document.getElementById('insertBtn').addEventListener('click', () => {
  insertKey(document.getElementById('keyInput').value.trim());
});
document.getElementById('lookupBtn').addEventListener('click', () => {
  lookupKey(document.getElementById('keyInput').value.trim());
});
document.getElementById('deleteBtn').addEventListener('click', () => {
  deleteKey(document.getElementById('keyInput').value.trim());
});
document.getElementById('resetBtn').addEventListener('click', () => {
  tableA.fill(null); tableB.fill(null);
  lastEvicted = { A: [], B: [] };
  lastFound = { A: [], B: [] };
  document.getElementById('log').innerHTML = '';
  setStatus('Tables cleared.', '');
  renderTables();
});
document.getElementById('keyInput').addEventListener('keydown', e => {
  if (e.key === 'Enter') insertKey(document.getElementById('keyInput').value.trim());
});

// Seed with a few initial keys
['cat', 'dog', 'fox', 'owl'].forEach(k => insertKey(k));
setStatus('Try inserting more keys and watch the eviction chains!', 'info');
Result
Console

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)O(1) is guaranteed. If an eviction cycle is detected the tables are rebuilt with new hash functions (a rehash).

The Real Complexity

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

  • Lookup: worst-case O(1)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)O(1). Check both slots, remove. No tombstones, no cascading cleanup.
  • Insertion: O(1)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)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)O(n)) or open addressing with probing (worst-case O(n)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cuckoo-hashing/Content licensed under CC BY-NC 4.0.