Cuckoo hashing

An ordinary hash table is fast on average but promises nothing about the worst case: a chain or a run of occupied cells sometimes stretches out. Cuckoo hashing does promise: the key sought lies in one of two places, and there is nowhere else to look. The price is paid on insertion. If both of a key's places are taken, it evicts one of the tenants, like a cuckoo chick, and that one flies to its second nest, possibly evicting the next one. Below are two tables of ten nests and the names of towns.

While there are few names, almost all settle at once. Closer to half full, chains of evictions begin, and around half one of the names finds no place at all: the evictions go round in a circle. The lines between the nests explain why: in the piece of the graph where this happened, there are now more names than nests.

The idea

Cuckoo hashing keeps two tables and two hash functions: the key x can live only in cell h₁(x) of the first table or in cell h₂(x) of the second. A lookup checks both cells: two probes in the worst case. An insertion puts the key into whichever of the two is free; if both are taken, it evicts the tenant of the first, the tenant moves to its place in the second table, evicts the next one from there, and so on until someone finds an empty cell. If the chain gets too long, the table is rebuilt with new hash functions.

The cuckoo graph

Draw the cells as vertices and each key as an edge between its two cells. This gives the cuckoo graph, the lines in the scene. To lay the keys out in cells means to give each edge to one of its ends so that each vertex has at most one edge. When is this possible?

Insertion with evictions looks for such a layout on the fly: a chain of evictions is a path along the edges of the graph. In a tree or a piece with one cycle it finds a free vertex. In a piece with more edges than vertices there is no free vertex, and the chain goes round in a circle until it is stopped.

In the scene this shows as dots on the lines. A dot sits at the end where the name lives, and each nest has at most one dot. While a piece has no more lines than nests, the dots can be placed; when the lines outnumber the nests, the piece turns red, and one of the lines has no dot: that name is left without a nest.

When the chain does not end

How is an insertion to know it is time to give up? Waiting for the chain to come back to the start is not enough: even in a piece that has room, it can go round a cycle, come back to the new key, evict it to its second nest and from there go off along another branch to a free vertex. It is endless only in an overfull piece, where there is no free vertex. In practice the chain is cut off at a number of evictions chosen in advance: in Pagh and Rodler's paper it grows as the logarithm of the table size, in the listing below it is 500.

A cut-off insertion leaves one tenant without a place, and there are two ways out. The first is to rebuild the table with new hash functions: the new cuckoo graph most likely has no overfull pieces. Below the threshold this happens so rarely that on average it costs almost nothing. The second is a stash: a small separate list for a few keys that found no place. A lookup checks it too, and Adam Kirsch, Michael Mitzenmacher and Udi Wieder showed in 2008 that for ordinary cuckoo hashing with two tables a stash of s keys reduces the probability of a rebuild from about 1/n to 1/n^s+1. Three or four places in the stash are enough for rebuilds practically never to happen.

The worst case of a lookup stays constant: two cells and a stash of a few keys. Both cells can be read from memory at once: the address of the second does not depend on the contents of the first, the processor does not wait for one to start the other, and two reads cost almost as much as one.

Exactly one half

So when do overfull pieces appear in the graph? With two tables of r cells, the cuckoo graph resembles a random graph with 2r vertices and n edges. Random graphs have a famous threshold, discovered by Paul Erdős and Alfréd Rényi in 1960: while there are fewer edges than half the vertices, all pieces are small, and almost all are trees, occasionally with one cycle; as soon as the edges pass half the vertices, a giant piece appears, with many cycles and more edges than vertices. For cuckoo hashing, “fewer edges than half the vertices” is a load n / 2r below 1/2.

Below the threshold an insertion costs O(1) on average: Rasmus Pagh and Flemming Friche Rodler, who devised the method in 2001, proved that the expected chain length is bounded by a constant and a rebuild is rarely needed. Above the threshold the table breaks almost surely. The scene shows this cliff for tables of 4096 cells. For two tables with single cells it is smeared out, roughly from 40 to 57 %: the table is small, and randomness in its graph is noticeable. For three tables and for buckets, the share of tables that hold everything drops from one to zero within two or three percent of load.

Half the table standing empty is expensive. The threshold is raised in two ways, and both show in the scene. Three hash functions and three tables give a key three nests, and the threshold rises to about 0.918. Buckets of four keys instead of single cells, with two hash functions, raise it to about 0.98. A lookup still looks in a constant number of places: three cells, or two buckets of four, eight cells that lie next to each other in memory.

Code

The listing puts the town names of GeoNames, 42,311 distinct ones, into cuckoo tables of three kinds with 32,768 cells until the next name no longer fits. The tenant to evict is chosen at random; after 500 evictions in a row the insertion gives up. The hash functions are FNV-1a and the splitmix64 mixer with different constants for different tables. At the end the program checks that every inserted name is found, except the one left without a place.

42311 distinct names, 32768 slots, up to 500 evictions per insert
tables x slots per bucket     stored    load  kicks per key
2 x 1                          16467   0.503           0.29
3 x 1                          29504   0.900           1.95
2 x 4                          31703   0.967           1.64

Two tables with single cells break at a load of 0.503, right at the threshold. Three tables get to 0.900, buckets of four to 0.967; they fall short of the theoretical 0.918 and 0.98 because the table is finite and the chain is cut off at 500 evictions. There are fewer than two evictions per key on average even at the very edge.

What it costs

Compare with an ordinary table. Linear probing at 90 % load spends about 50 probes on an unsuccessful lookup on average, and chaining fewer than two on average, but with no upper guarantee. Cuckoo hashing with buckets of four at 95 % never looks at more than the eight cells of two buckets.

Insertion below the threshold is O(1) on average; deletion just removes the key from its cell, with no tombstones as in open addressing. The price is the chance of failure: once in a while an insertion loops, and the whole table is rebuilt with new hash functions in O(n). So cuckoo hashing is chosen when the worst case of lookup matters, not of insertion: in network hardware and packet processing there is a lookup for every packet, while insertions are rare.

Where it is used

• Packet processing. The hash library of DPDK, on which software routers and load balancers are built, resolves collisions by the cuckoo algorithm according to its documentation: a key has a primary and a secondary bucket, and if there is no room in the primary one, one of the tenants moves to its secondary.
• Caches. MemC3, a 2013 variant of memcached, replaced chaining with cuckoo hashing with buckets and optimistic locking: readers do not wait for the writer.
• Filters. The 2014 cuckoo filter keeps short fingerprints instead of keys in buckets of four. It computes the second bucket from the first and the fingerprint, so a move is possible without the key itself. Unlike a Bloom filter, it can delete, and at a low false positive rate it is also more compact.
• Two choices. The idea “each key has two places” is the same as in the power of two choices, except that there keys are not moved, and here they are.

History

Rasmus Pagh and Flemming Friche Rodler presented cuckoo hashing in 2001 at the ESA symposium on algorithms and named it after the bird that lays its egg in another bird's nest, whose chick pushes out the hosts' own. They were looking for a dictionary with constant-time lookup in the worst case that would be simpler than dynamic perfect hashing and use no more memory than a search tree. Nineteen years later the paper received the ESA Test-of-Time Award. The thresholds for three or more hash functions and for buckets were computed exactly later, in 2009–2010, by several groups at once.

Problems

The problem asks how many keys fit into the table at once if they may be laid out any way you like: a direct consequence of the theorem on pieces of the graph. On town names the answer shows what “above the threshold” means.