Max Countryman

Cuckoo hashing

Cuckoo hashing feels almost like a vacancy chain in reverse. With hermit crabs, an empty shell starts a chain of moves.

In cuckoo hashing, each key has two possible slots. A new arrival can displace an occupant into its alternate slot, which may displace another, until one finds an empty slot.

X displaces A, A displaces B, and B moves into the vacant slot.
X displaces A, A displaces B, and B moves into the vacant slot.

A vacancy pulls a chain of moves; an arrival pushes one.