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.
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.
Controls let you insert and delete keys, set the number of hash functions and table size to explore different load factors, step through eviction chains one displacement at a time, and manually trigger a rehash to see the table redistribute all keys under freshly chosen hash functions.
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.
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.
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.
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 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.