Chained hashing — where it appears
Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.
A bucket that becomes a tree
Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Load factorCacheCuckoo hashingHash tableLinear probingLocalityMemory layoutMiss rateWorst case guaranteeAccess patternDistributionHash collision