↩ back to Hash-Based

Cuckoo Hashing

The site's hash table handles collisions by chaining: everything that lands in the same bucket queues up in a list, so get is O(1) on average but degrades to O(n) in the worst case if one chain grows long. Cuckoo hashing removes that worst case outright. Every key gets exactly two possible homes — one slot in table 1, picked by hash function h1, and one slot in a separate table 2, picked by an independent hash function h2 — and a key is never stored anywhere else. get(key) only ever has to check those two exact slots: table 1's h1(key), then, if that's not a match, table 2's h2(key). Two lookups, always, whether the key is there or not, regardless of how the table got built. That's a genuine worst-case guarantee, not a probabilistic average.

The name comes from the cuckoo bird, which lays its egg in another bird's nest and lets the hatchling shove the original egg out. Inserting a key works the same way: try its slot in table 1. If that slot's empty, done. If it's occupied, evict whoever's there, put the new key in its place, and go place the evicted key in table 2 at its own h2 slot — which might itself be occupied, evicting a third key back into table 1, and so on. Most inserts settle in one or two hops. But a chain of evictions can also loop back on itself and never find an empty slot — the demo below includes a real example of that happening, not a staged one, and shows what the algorithm does about it.

Try it

Put a key/value pair, get one back, or delete it. The log traces every hop: which slot in which table it tried, whether that slot was empty or already held someone else, and — if it had to evict — where the displaced key went next. The sample below loads five keys with one real cascade already baked in (putting dog evicted owl out of table 1 into table 2). Put elk next and watch a longer three-hop cascade still resolve cleanly. Then put ram: it touches off a chain that cycles through the same handful of keys without ever finding an empty slot, blows through the kick budget, and forces a live rehash — both tables double in size, the second hash function gets a fresh seed, and every entry (the stuck one included) gets reinserted into the bigger table from scratch.

Core operations

• h1(key) / h2(key) — two independent hash functions (different multiplier, different seed), each folding the key to a number and reducing it into range with % size. O(k) for a key of length k.
• get(key) — check table 1's h1(key) slot; if it doesn't match, check table 2's h2(key) slot. Exactly one or two direct lookups, no scanning, no chain to walk. O(1) worst case.
• put(key, value) — update in place if the key's already at one of its two slots. Otherwise place it at table 1's h1 slot, evicting whatever's already there if occupied, then relocate the evicted key into table 2 at its own h2 slot — evicting again if needed, alternating tables. O(1) expected; can cascade, bounded by a fixed "kick budget" before the table gives up and rehashes.
• delete(key) — the same two-slot check as get; clear whichever slot matches.

Reference implementation

class CuckooHashTable {
  #size;
  #t1;
  #t2;
  #salt2 = 17;
  #maxKicks;

  constructor(size = 8) {
    this.#size = size;
    this.#t1 = new Array(size).fill(null);
    this.#t2 = new Array(size).fill(null);
    this.#maxKicks = 2 * Math.ceil(Math.log2(size * 2)) + 1;
  }

  #hash1(key, size = this.#size) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return h % size;
  }

  #hash2(key, size = this.#size) {
    let h = this.#salt2;
    for (const ch of String(key)) h = (h * 37 + ch.charCodeAt(0) + 7) >>> 0;
    return h % size;
  }

  get(key) {
    const i1 = this.#hash1(key);
    if (this.#t1[i1] && this.#t1[i1][0] === key) return this.#t1[i1][1];
    const i2 = this.#hash2(key);
    if (this.#t2[i2] && this.#t2[i2][0] === key) return this.#t2[i2][1];
    return undefined;
  }

  has(key) {
    const i1 = this.#hash1(key);
    if (this.#t1[i1] && this.#t1[i1][0] === key) return true;
    const i2 = this.#hash2(key);
    return !!(this.#t2[i2] && this.#t2[i2][0] === key);
  }

  delete(key) {
    const i1 = this.#hash1(key);
    if (this.#t1[i1] && this.#t1[i1][0] === key) { this.#t1[i1] = null; return true; }
    const i2 = this.#hash2(key);
    if (this.#t2[i2] && this.#t2[i2][0] === key) { this.#t2[i2] = null; return true; }
    return false;
  }

  put(key, value) {
    const i1 = this.#hash1(key);
    if (this.#t1[i1] && this.#t1[i1][0] === key) { this.#t1[i1][1] = value; return; }
    const i2 = this.#hash2(key);
    if (this.#t2[i2] && this.#t2[i2][0] === key) { this.#t2[i2][1] = value; return; }
    this.#insert(key, value, 0);
  }

  #insert(key, value, kicks) {
    if (kicks > this.#maxKicks) { this.#rehash(); this.#insert(key, value, 0); return; }
    const i1 = this.#hash1(key);
    if (!this.#t1[i1]) { this.#t1[i1] = [key, value]; return; }
    const evicted = this.#t1[i1];
    this.#t1[i1] = [key, value];
    const i2 = this.#hash2(evicted[0]);
    if (!this.#t2[i2]) { this.#t2[i2] = evicted; return; }
    const evicted2 = this.#t2[i2];
    this.#t2[i2] = evicted;
    this.#insert(evicted2[0], evicted2[1], kicks + 1);
  }

  #rehash() {
    const entries = [...this.#t1, ...this.#t2].filter(Boolean);
    this.#size *= 2;
    this.#salt2 = (this.#salt2 * 2654435761 + 1) >>> 0;
    this.#t1 = new Array(this.#size).fill(null);
    this.#t2 = new Array(this.#size).fill(null);
    this.#maxKicks = 2 * Math.ceil(Math.log2(this.#size * 2)) + 1;
    for (const [k, v] of entries) this.#insert(k, v, 0);
  }
}

A key is only ever evicted out of a slot it's actually occupying — #insert checks table 1 first, then table 2, and only recurses (another "kick") once both checks in one pass came up occupied. #rehash grabs every surviving entry out of both tables, doubles the size, mutates #salt2 so #hash2 spreads keys differently next time, and reinserts everything — the key that triggered the rehash included, via the retry after #rehash() returns. Verified against a plain-Map reference model over 1,000 randomized trials of 250 interleaved put/get/has/ delete calls each (small key spaces to force frequent evictions and rehashes), checking every result against the model after every call, plus that get and has never need more than 2 slot checks to answer — see /tmp/cuckoo_ref_test.js, scratch, not committed. Separately confirmed the page's own fox/owl/ cat/dog/bee/elk/ram walkthrough by hand: table doubles from 8 to 16 slots on ram, and all seven keys are still correctly found afterward.

Pitfalls

No cap on displacement kicks means a real infinite loop, not a slow one. This isn't a hypothetical: removing the #maxKicks cap from the reference implementation above and rerunning the page's own sample sequence (fox, owl, cat, dog, bee, elk, then ram) makes the eviction chain cycle through the same six keys — cat, elk, dog, owl, and ram chasing each other between the same handful of slots — for over 1,000 kicks with no sign of stopping; it's a genuine cycle in the eviction graph, not merely a long chain that would eventually resolve given more patience. With the cap in place, the real chain runs 10 kicks (44 individual hop-lines, truncated in the log display) before the table gives up and rehashes — and the rehash isn't cosmetic: verified all 7 keys, including the one still "in hand" when the cycle was detected, land correctly and stay within 2 probes each in the doubled 16-slot table afterward.

Cuckoo hashing needs more headroom than chaining. The site's chaining hash table tolerates a load factor up to 0.75 before resizing — a chain just gets one entry longer past that point, no correctness risk. Cuckoo hashing with two hash functions has no such graceful degradation: as the combined tables fill up, the odds of a displacement chain running into a cycle like the one above rise sharply, and the 7-key example above happens at just 7 of 16 slots filled (44% — nowhere near 0.75) once two particular keys collide badly enough. Production cuckoo hash tables generally keep load under roughly 50%, or use more than two hash functions (or "buckets" holding a few keys each per table) to push that ceiling higher — this page keeps it to the textbook two-table, one-slot-per-table version to keep the mechanics visible.

h1 and h2 have to actually be independent. If both hash functions folded a key the same way, every key's table-1 slot and table-2 slot would sit at the same index, and an eviction in table 1 would just bounce the evicted key into an already-doomed spot in table 2 — collapsing the two-table scheme into something worse than a single plain table, since now both a key's possible homes collide whenever one does. The reference implementation above avoids this by using a different multiplier (31 vs. 37), a different accumulator seed, and a mutable salt that changes on every rehash — not just two superficially different-looking formulas that happen to correlate.

Where cuckoo hashing shows up

• Cuckoo filters. A probabilistic set-membership structure built directly on this page's displacement idea — the successor to the site's own Bloom filter in situations that also need deletion, which a classic Bloom filter can't support without extra machinery.
• Hardware and router lookup tables. Network switches doing forwarding-table lookups in silicon want a fixed, small, predictable number of memory accesses per lookup — exactly the two-probes-always guarantee this page's get provides, where an average-case structure's occasional slow chain would be an unacceptable latency spike.
• Any latency-sensitive lookup path where a rare but real O(n) worst-case chain (as in separate chaining) is worse than a slightly higher constant memory cost — the same trade-off AVL trees make against plain BSTs, just for hashing instead of ordered search.

Complexity

Time: get and delete are O(1) worst case, not merely on average — two fixed slot checks, full stop, regardless of how the table was built. That's the whole point of this structure over the site's chaining hash table, which is only O(1) on average and degrades to O(n) if one chain grows long. put is O(1) expected — most inserts resolve within one or two evictions — but has no small fixed worst-case bound: a displacement chain can run all the way to the kick cap and force an O(n) rehash, reinserting every entry (the "no cap means a real infinite loop" pitfall above walks through exactly that call). Space: O(n), but with a lower practical ceiling than chaining's — two hash functions realistically need the combined tables to stay well under full before cycles become likely (the "needs more headroom" pitfall above), so cuckoo hashing spends more unused capacity per stored key than chaining does, in exchange for turning get's worst case from probabilistic into guaranteed.

This is one of four collision-resolution strategies the site covers for the same put/get/delete contract — the site's chaining hash table, Robin Hood hashing, and hopscotch hashing are the other three. Hopscotch hashing is the closest comparison: it matches this page's hard worst-case bound on get without needing a second table, at the cost of a trickier put. See Choosing a Hash Table Collision Strategy for the full four-way comparison.