Cuckoo hashing — where it appears
Named by 19 essays across 2 fields — each of them below, with the objects they name alongside it.
An insertion that can fail
Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.
The evidence a filter cannot remove
A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.
More hashes or wider buckets
A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
Two probes are two misses
Cuckoo hashing's lookup reads at most two slots, and at a load of 0.45 it reads 1.27 on average where linear probing reads 1.39. Replayed through a cache, it misses 1.18 times a lookup where linear probing misses 0.98. The table that wins the count the analysis uses loses the count the machine charges, because two slots in unrelated places are two cache lines, and a run of adjacent slots is usually one.
The bucket that fits a line
Make each of a cuckoo table's two candidates a bucket of eight slots laid out on one cache line, and no lookup ever touches more than two lines, the table builds past a load of 0.95, and at that load it misses 1.21 times a lookup where linear probing misses 1.79. The prediction that it would lose to linear probing at low loads was wrong — it misses less at every load measured, 0.94 against 0.96 at 0.3 — because a key it holds almost never lives in its second bucket. The guarantee belongs to the alignment, not the bucket; eight slots on lines of four put a lookup on four lines.
A tag that answers more than yes
A byte of hash in front of each entry has one bit of output per slot: this tag matches or it does not. Cut it from an ordered field instead and a bucket's tags can be kept sorted, so a lookup stops at the first tag above its own — 8.97 comparisons for an absent key instead of 14.43, for 3.55 tag-byte shifts an insertion. The obvious ordered field is the trap. Take the tag from the bucket index's own bits and every key in a bucket shares them: 5.74 entry reads on an absent key instead of 0.054, a hundred and seven times more.
Entries found by the rank of their tag
A bucket whose tags are kept sorted is an index: the position a tag is found at is its rank, and a rank can address an entry. Drop the fixed slots and pack each bucket's entries in tag order, and a cuckoo table of 32-byte records holds 36.1 bytes a key at half load where slots hold 66.1, and 34.3 against 36.7 at 0.9. Every insertion pays for it by moving the entries after its rank: 99 bytes against 36 at half load, 586 against 105 at 0.9. The prediction that packing would lose above 70% load was about the wrong quantity.
The slack an insertion can reach
A cuckoo table whose entries are packed by tag rank holds half the bytes of a slotted one at half load, and pays by shifting entries on every insertion. It was proposed to keep a few spare entries at the end of each group's region. Charged the copies a full region costs, that slack helps only with the copies: at groups of 16 buckets an insertion still moves over a thousand bytes, against 36 for slots. The same slack divided among the buckets, with an insertion borrowing the nearest free entry, moves 347 — and the group size, which multiplied every earlier cost, stops mattering.
Spare where a bucket can use it
A cuckoo table packed by tag rank keeps a few spare entries in each region of sixteen buckets, and every time a region runs out it divides its spare among the buckets again. Divided evenly, most of the spare ends up in buckets that are already full, which never grow — they kick. Divided in proportion to where insertions have been landing, as proposed, more of it does, and an insertion at 90% load moves 1,159 bytes against 1,005. Divided by the room each bucket has left, only 3% of it is stranded, and at 95% load an insertion moves 10 to 17% less than with an even division. None of the three comes near the half-load figure, because all of the growth from half load to 90% is the cuckoo kicks' own cost.
The keys a capped chain leaves behind
At 95% load five sixths of the bytes a packed cuckoo table moves on an insertion are its kick chain, and the chain is mostly tail: capping it at two kicks removes 72% of the kicks. The proposal was to put the key still displaced into an overflow held in its region's spare, and it predicted that the bytes moved would halve. They fall by 13%. A key placed in the spare costs 1,819 bytes to insert, six kicks' worth, because the free slot nearest the region's end is far away and every entry between moves. The same cap with the overflow in a separate block halves the bytes as predicted, for a byte a key and an overflow that every failed lookup has to read.
The lookups a filter turns away
A capped cuckoo table keeps its stopped keys in an overflow block a region, and at 95% load every lookup for an absent key reads those blocks — 1.93 of them, because a key could have been stopped in either of its buckets' regions. A Bloom filter over each region's overflow at eight bits a key was predicted to let about 2% of those lookups through. It lets 2.07% through, and the prediction was right for two wrong reasons that cancel. Filing every stopped key under its first bucket halves the rest, and then the lookups the filter cannot help, the 3.9% of keys that really live in the overflow, are what is left to pay.
The block already open
A cuckoo table that caps its kick chain at two keeps the keys it stopped in an overflow block a region, and with a filter in front of each block a successful lookup's cost is set by the share of keys living there: 3.7% after one fill to 95%. Under deletions and insertions in equal numbers it was predicted to climb without limit unless every deletion moved a stopped key home. It does not climb without limit; it settles, at 9.2%. Homing at every deletion holds it at 4.0%, as predicted — by reading a block on 98% of deletions, and by sending a quarter of the insertions that follow to the overflow, because a key moved home takes the slot the next key needed. Moving keys home only when their block is already open for another reason holds the overflow at 4.9% for 0.07 blocks a pair more than leaving keys alone, and costs less than leaving keys where they stopped from one and a half successful lookups a deletion.
Room the chains could not reach
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys outside their buckets while 13.8% of its entries stand empty. Keeping a few entries in each region aside for the keys the cap stops, at the same memory, was predicted to remove most of the overflow for a tenth of a kick an insertion. It removes none of it: the share outside the buckets stays at 9.2% with up to eight entries kept back, because a key is stopped by the pair of buckets its chain visits, never by a region short of room. What the reserve changes is where the stopped keys sit, and that is worth having. Read with the region's header, four entries a region take the overflow blocks from 9.2% of keys to 6.1% when keys stay and from 4.9% to 2.3% when keys go home with an open block, for no kick anyone can measure — until the reserve takes room the chains were using, at sixteen entries when keys stay and at eight when they go home.
A kick that looks before it moves
A cuckoo table that caps its kick chain at two, churned at 95% load, keeps 9.2% of its keys in overflow while 13.8% of its entries stand empty. A kick that first reads the other buckets of a full bucket's residents and moves one with room was predicted to remove most of the overflow for about three bucket reads an insertion that meets a full bucket. One level of looking leaves 0.20% in overflow and two levels leave none, for 5.7 reads an insertion that meets a full bucket. But blind kicks under a cap of 32 leave 0.02% for the same 4.2 reads an insertion, so the empty room was never out of a blind chain's reach: the cap of two kept it empty. What looking saves is the thing the cap was introduced to save. The blind chain that reaches the room rewrites 4.2 entries an insertion; the look rewrites 1.8, and at 97% load 2.1 against 7.2.
A look that spreads the room
A cuckoo table's insertion that meets a full bucket can look at its residents' other buckets before moving anyone, and the look that stops at the first with room leaves 0.20% of keys in overflow at 95% load. Moving the resident to the emptiest of the eight instead was predicted to leave none, for one and a half more reads, by spreading the table's free slots rather than consuming them where they are found. It leaves 0.08% for 2.8 more reads, and at 97% load it barely helps. The room does spread, and spread room is still room a look cannot reach: one more level of looking, at fewer reads, leaves none.
Overflow holds the old keys
A cuckoo table that kicks blind under a cap of two leaves 9% of its keys in overflow, and every way of searching harder for room leaves fewer. Charged for its lookups as well as its insertions, the overflow was predicted to make a deeper search pay from ten lookups an insertion. It does not: blind kicks under a cap of two are the cheapest table up to thirty lookups an insertion when stored keys are asked for evenly, and at every mix measured when they are asked for by recency. Searching harder also moves keys into their second buckets, which every lookup pays for, and the keys a kick leaves in overflow are the old ones, not the new.
A kick that moves the oldest
A cuckoo table full to 95% makes room for a new key by kicking a resident of the full bucket to its other bucket, and blind kicks under a cap of two were the cheapest design for lookups as well as insertions — with every key drifting outward with age, so that overflow held the oldest keys. Choosing which resident to kick, the oldest rather than one at random, was predicted to bring a lookup asked by recency from 1.09 reads to about 1.04 and to change nothing for even lookups. It brings recency to 1.040, and even lookups fall too, from 1.420 to 1.331, because a table that always kicks the oldest sorts itself by age: the newest three tenths of the keys almost never leave their first buckets, and the oldest tenth is 56% in overflow. It is the cheapest design at every mix of lookups to insertions measured. The risk named, chains that lengthen, arrives only with the cap: at a cap of 32 the oldest kick leaves 6.6% of keys in overflow where random kicks leave none.
An old key is a crowded key
A cuckoo table that makes room by kicking each full bucket's oldest resident keeps its newest keys at home and brings a lookup asked by recency to 1.04 reads, the cheapest design measured — but only at a cap of two kicks. At a cap of 32 it leaves 6.6% of its keys in overflow where random kicks leave none, and the explanation offered was a loop: an old key kicked to its other bucket is old there too, and the next chain moves it back. Sparing every key the chain has already moved changes nothing at caps of two and eight and makes cap 32 slightly worse, 7.1%; sparing the last sixteen insertions' moves gets it to 5.0%. There was no loop. A kicked resident's other bucket has room 22% of the time when the resident is chosen at random and 7% when it is the oldest: in a table that always moves the oldest, a key grows old because both of its buckets stay full. Kicking the older of four drawn at random keeps much of the gain at a long cap, 1.055 reads by recency and 0.5% overflow, and still costs more than the oldest kick at a cap of two.
Named alongside it
The objects these essays reach for when they reach for this one.
Hash tableLoad factorDesign parameterMeasured countHonest limitLocalitySpace accountingCacheWorkloadData movementFingerprintRank