THE FOLD / LOOT / THE-STASH / THE ROBIN HOOD
THE ROBIN HOOD
steal from the rich to even the probes
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Robin Hood hashing is an open-addressing scheme that steals from the rich to give to the poor. In ordinary linear probing, some keys sit right at their home slot while others get pushed far away, so probe lengths vary wildly. Robin Hood equalizes them: when inserting a key that has probed farther than the key already sitting in a slot, it evicts the richer resident (the one closer to its home) and carries it onward. The result is the same set of keys, but with the variance of probe lengths minimized — no key is left starving while another sits pretty, so lookups stay fast even at high load.
LIT verified live: over 400 tables at 85% load, every key remains retrievable, and both the variance and the maximum of the probe lengths are ≤ plain linear probing on the same keys (window.__robin_hood). FIG no framing; the displacement insert, the lookup, and a linear-probing baseline run in-browser.
LIT verified live: over 400 tables at 85% load, every key remains retrievable, and both the variance and the maximum of the probe lengths are ≤ plain linear probing on the same keys (window.__robin_hood). FIG no framing; the displacement insert, the lookup, and a linear-probing baseline run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-stash — even out the stash so no key hoards a short probe while another is banished far away. AVAN (AI) built the instrument: the steal-from-the-rich insert, the probe-aware lookup, and the linear-probing comparison.
Credit as content: Pedro Celis (Robin Hood Hashing, 1986). The weave: David names the stash; I confirm the displacement rule keeps every key findable while shrinking the spread of probe lengths.
Credit as content: Pedro Celis (Robin Hood Hashing, 1986). The weave: David names the stash; I confirm the displacement rule keeps every key findable while shrinking the spread of probe lengths.
3 ONE DIMENSION
Slots with each key's probe distance; when a poorer key meets a richer resident, they swap — evening the distances.
4 TWO DIMENSIONS · INTERACTIVE
Fill a table; the probe-length histogram stays tight, with lower variance and max than linear probing.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the balanced probe-length distribution.
AVAN’s addition (the inverse-companion): don’t let the first arrival keep the short probe — steal it. The inverse of ‘probe forward and settle’ is ‘if you’ve travelled farther than the resident, take its slot and carry it on’ — minimizing probe variance. Magenta is a long, starving probe; green is the evened-out distribution. Fairness by eviction.
LIT Genuine Robin Hood hashing (Pedro Celis, 1986). Verified live: over 400 tables at 85% load factor, every inserted key is retrievable, and both the variance and the maximum probe length are ≤ plain linear probing on the identical key set (window.__robin_hood.allFound, .varLower, .maxLower).
FIG No framing: the displacement insert, the probe-aware lookup, and a linear-probing baseline run in-browser. The AVAN inverse is honest — instead of letting the first arrival keep its short probe, a later key that has travelled farther steals the slot and carries the resident onward, minimizing probe variance. Magenta is a long starving probe; green is the evened-out distribution. Fairness by eviction.
FIG No framing: the displacement insert, the probe-aware lookup, and a linear-probing baseline run in-browser. The AVAN inverse is honest — instead of letting the first arrival keep its short probe, a later key that has travelled farther steals the slot and carries the resident onward, minimizing probe variance. Magenta is a long starving probe; green is the evened-out distribution. Fairness by eviction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-STASH · David Lee Wise (ROOT0), with AVAN