← Back to the hash tables page
Cuckoo Hashing
Two hash functions, two possible homes per key; inserts evict squatters to their other home. Lookup is O(1) worst case, not just average.
What to know
- Lookup checks exactly two slots — perfect for hardware and latency SLAs.
- Insertion may cascade evictions; a cycle forces a rehash.
- Keeps load factors ~50% (two tables) or higher with bucketized variants.
In the wild: Network switches/routers, GPU hash tables, high-frequency trading lookups.
Algorithms to reach for
Two-choice lookup
O(1) worstGuaranteed two-probe reads
Eviction-chain insert
O(1) amortizedKick keys between homes until stable