Home▸Algorithms & AI▸Cuckoo Hashing: Evicting Your Way to Fast Lookups

🐦 Cuckoo Hashing: Guaranteed Constant-Time Lookups

Explore cuckoo hashing, a collision-resolution scheme that uses two hash functions and two tables so every key has exactly two possible homes, guaranteeing fast worst-case lookups.

Algorithms & AI3DModerate60 FPS

This simulation demonstrates how cuckoo hashing places keys into two hash tables using two hash functions, how inserting a new key can trigger a cascading chain of evictions as displaced keys bump other keys from their alternate slots, and how the table detects and resolves a cycle by rehashing everything with new hash functions when evictions cannot settle.

🔬 What It Demonstrates

🎮 How to Use

Add keys one at a time and watch each insertion animate: the key is hashed to its first candidate slot, and if that slot is occupied, the displaced key is evicted and immediately reinserted into its own alternate slot, continuing until a slot is found empty or a cycle is detected. Adjust the table size to change the load factor and observe how eviction chains grow longer and rehashing events become more frequent as the table approaches roughly fifty percent full. Trigger a lookup on any key to see that it never requires checking more than its two designated slots.

💡 Did You Know?

Did you know that cuckoo hashing was only introduced in 2001 by Rasmus Pagh and Flemming Friis Rodler, making it far younger than chaining or linear probing, yet it is now used in real systems ranging from network routers doing high-speed packet lookups to distributed key-value stores, precisely because it offers a hard guarantee on worst-case lookup time that older schemes cannot promise.

⚙ Under the hood

Explore cuckoo hashing, a hash table scheme where colliding keys evict each other between two tables, guaranteeing fast constant-time worst-case lookups.

cuckoo-hashinghash-tablesdata-structurescollision-resolutionalgorithmscomputer-scienceload-factoreviction

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install