1. One-Liner
Cuckoo hashing gives each key two possible slots; on collision the occupant is evicted and reinserted—like a cuckoo pushing eggs—until success or a detected cycle triggers rehash.
2. The Problem It Solves
Open addressing can probe long; chaining uses extra pointers. Cuckoo offers O(1) worst-case lookup with two hashes and constant slots per key—at the cost of tricky inserts.
3. The Core Idea
Try slot A or B; if full, kick the old key to its alternate location; repeat. Lookup always checks at most two cells.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | Compute i1=h1(k), i2=h2(k) |
| 2 | Prefer empty among the two |
| 3 | Else evict, insert k, reinsert evicted |
| 4 | Cycle / max steps → rehash bigger table |
5. Dry Run Example
Two slots per key; insert chain evicts along path until placement or rehash—lookup still 2 probes max.
6. Key Properties
| Property | Value |
|---|---|
| Lookup | O(1) worst-case (two cells) |
| Insert | Amortized expected O(1), rehash rare with low load |
| Load | Typically <50% for two tables |
7. Where It Is Used
| Domain | Use |
|---|---|
| Networking | High-speed exact lookups |
| Libraries | Specialized maps / GPU-friendly variants |
8. Interview Tips
Two hash functions, eviction path, load threshold, rehash on failure—core talking points.
9. Comparison with Other Algorithms
| Scheme | Lookup worst |
|---|---|
| Cuckoo | O(1) cells checked |
| Linear probe | O(n) chain |
| Chaining | O(length of list) |
10. Complexity
| Metric | Value |
|---|---|
| Lookup | O(1) time, 2 memory refs |
| Insert | Expected O(1), rehash amortized |
Implementation Example (PYTHON)
class Cuckoo:
def __init__(self, m=16):
self.m, self.t = m, [None] * m
def _h(self, k, z): return (hash(k) + z * hash(str(k))) % self.m
def put(self, k, v, maxloop=64):
cur, val = k, (k, v)
for _ in range(maxloop):
for z in (0, 1):
i = self._h(cur, z)
if self.t[i] is None:
self.t[i] = val; return
i = self._h(cur, 0)
self.t[i], val = val, self.t[i]
cur = val[0]
raise RuntimeError('rehash')