Cuckoo Hashing Visualization | Two Tables, Eviction Chains, Rehash

The idea: every key has exactly two homes

Cuckoo hashing is a hash table with two tables, T1 and T2, and two hash functions. A key k can live in only two places: slot h1(k) of T1 or slot h2(k) of T2. To find it you look in those two slots and nowhere else, so a lookup never takes more than 2 probes.

Key 76 with two arrows: h1(76) = 76 mod 10 = 6 points to slot 6 of table T1, and h2(76) = floor(76/10) mod 10 = 7 points to slot 7 of table T2. Both slots are highlighted — Key 76 may live only in T1[6] or T2[7], so find(76) checks those two slots and stops.

The page has two tables of m = 10 slots. It uses h1(k) = k mod m and h2(k) = ⌊k/m⌋ mod m. With m = 10 these are just the last digit and the tens digit of the key, so you can check every step in your head. Under each stored key, a grey number shows its other home. Pick a key and press Insert, Find or Delete, or run a demo.

Find and delete: two probes, worst case

find(k) checks T1[h1(k)] first and then T2[h2(k)]. If k is in neither slot, it is not in the table. This is true for every key, at any load, so lookup is O(1) in the worst case, not only on average. Linear probing and chaining cannot promise that: a bad cluster or a long chain makes some lookups slow.

In Demo 1, find(31) hits T1[1] with the first probe. In Demo 2, 53 was pushed to T2, so find(53) sees 23 in T1[3] and finds 53 in T2[5]: 2 probes. delete(k) finds k and empties its slot. No tombstone is needed, because no lookup ever scans past a slot. In Demo 5, after delete(53), find(53) checks its two slots and stops: a miss costs 2 probes too.

Insert: the eviction chain

insert(x) always puts x into T1[h1(x)]. If that slot is free, it is done. If another key y is there, x takes the slot anyway and kicks y out, as a cuckoo chick pushes the other eggs out of the nest. y then moves to its other home: T2[h2(y)] if it was in T1, T1[h1(y)] if it was in T2. If that slot is taken too, y kicks out its owner, and so on. The keys move back and forth between the tables until one lands in an empty slot. This is the eviction chain.

Before: T1[0] = 40, T1[6] = 26, T2[2] = 20. After insert(76): 76 goes to T1[6], 26 is kicked to T2[2], 20 is kicked to T1[0], and 40 is kicked to the empty T2[4]. Four numbered arrows show the chain — insert(76) from Demo 3: three kicks, alternating T1 and T2, until 40 finds an empty slot.

In Demo 3, 26, 20 and 40 are inserted first; 40 already kicks 20 to T2[2]. Then insert(76) starts a chain of 3 kicks: 76 → T1[6], 26 → T2[2], 20 → T1[0], 40 → T2[4]. Every key that moved is still in one of its two homes, so lookups stay at 2 probes.

Cycles and rehashing

Sometimes there is no free slot to reach. Keys 25, 125 and 225 all have h1 = 5 and h2 = 2: three keys share the same two slots, which is impossible. The chain would go around forever: 225 kicks 125, 125 kicks 25, 25 kicks 225, and so on. Real implementations stop after a fixed number of kicks (often called MaxLoop; here 6) and treat the chain as a cycle.

Then the table rehashes: it picks new hash functions and inserts every key again. Here the new functions come from doubling m to 20, so h2(k) = ⌊k/20⌋ mod 20 gives 25, 125 and 225 three different slots in T2 (Demo 4). Rehashing costs O(n), but it is rare when the table is not too full, so insert is still O(1) expected, amortized.

Left, m = 10: the slots T1[5] and T2[2] joined by three edges, one for each key 25, 125 and 225, marked as impossible. Right, m = 20 after rehash: T1[5] joined to T2[1], T2[6] and T2[11] by the edges 25, 125 and 225, marked as fine — Draw each slot as a node and each key as an edge between its two slots: more keys than slots in one group means a cycle that no chain can solve.

This drawing is the cuckoo graph. An insert succeeds as long as every connected group of slots has no more keys than slots. With random hash functions and two tables, that holds with high probability while the load n/2m stays below about 50%. Above that, cycles appear quickly.

Compared with other hash tables

	Separate chaining	Linear probing	Cuckoo (2 tables)
Lookup, worst case	whole chain, O(n)	whole cluster, O(n)	2 probes, O(1)
Insert	O(1)	O(1) expected	O(1) expected, amortized; rare rehash
Delete	unlink the node	needs tombstones	empty the slot
Usable load	above 1 is fine	up to about 70%	up to about 50%

The low load limit is the price of the worst-case lookup. Variants fix it: with buckets of 4 slots, or with 3 hash functions instead of 2, cuckoo tables work above 90% load. Cuckoo-style tables are used where a lookup must take a fixed time: network switches and routers, GPU and hardware hash tables, and cuckoo filters, which store small fingerprints in a cuckoo table and, unlike a Bloom filter, support delete.

See also Separate Chaining vs Linear Probing for the two classic ways to handle collisions, Closed Hash Tables for linear and quadratic probing and double hashing, and Bloom Filter for the membership filter that cuckoo filters compete with.

What the page leaves out

Real hash functions picked at random from a universal family (the page uses digits so you can check them); rehashing with new random functions at the same size, and growing only when the load is high; the MaxLoop bound of O(log n) from the analysis; bucketized and d-ary cuckoo hashing; the stash, a few extra slots that absorb rare failures; choosing which key to kick by random walk or breadth-first search; and concurrent cuckoo tables such as libcuckoo.