Cuckoo Hashing
Follow evicted keys between two hash tables and detect when a rehash is needed.
Free theory articleFollow evicted keys between two hash tables and detect when a rehash is needed.
Concept & interpretation
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches.
Experiment
Explore different insertion sequences to see how cuckoo hashing handles evictions and detects cycles:https://riano.app/module/cuckoo-hashing
- Select the Evictions option from the Keys dropdown and click Step to observe the chained displacements described in the worked example.
- Select the Impossible pair option and step through the insertions. Observe how keys 0, 25, and 50 all share the exact same hash locations:
h1(x) = 0andh2(x) = 0. - Notice that after reaching the displacement limit (10 steps), the status changes to Rehash required and the unplaceable key is moved to the overflow pool.