Cuckoo Hashing

Cuckoo hashing restricts each key to two candidate cells, moving collisions into insertion. Read it to separate worst-case lookup from expected amortized updates, replay an eviction chain, and see why empty space alone cannot guarantee a valid placement.

Reading focus: How two legal homes per key bound lookup while allowing insertion to displace residents. Why three keys sharing two candidate cells cannot fit, even in a mostly empty table. Which randomness and space assumptions support the update guarantee, and where historical benchmarks stop.

Journal of Algorithms 2004. Rasmus Pagh and Flemming Friche Rodler. 28 min read, easy difficulty.