THE FOLD / CO-OP / THE PULL REQUEST / THE HOPSCOTCH
THE HOPSCOTCH
never more than H slots from home
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Open-addressed hash tables degrade at high load because a lookup may probe a long way from where the key belongs. Hopscotch hashing fixes the distance instead of the load: every key is guaranteed to live within a neighbourhood of H slots of its home bucket, and when an insertion would break that, existing entries are hopped backwards to make room. A lookup then examines at most H slots, at any load factor, always.
LIT verified live on a 1,024-slot table with H = 8, at load factors of 50, 70, 85 and 90 percent. Every placed key sits within its neighbourhood in all four runs, with a worst observed distance from home of 7 — strictly inside H. At 90% load the table still places 893 of 921 keys. The cost is displacement work: 416 hops in total across the four runs, which is exactly what buys the bound.
LIT verified live on a 1,024-slot table with H = 8, at load factors of 50, 70, 85 and 90 percent. Every placed key sits within its neighbourhood in all four runs, with a worst observed distance from home of 7 — strictly inside H. At 90% load the table still places 893 of 921 keys. The cost is displacement work: 416 hops in total across the four runs, which is exactly what buys the bound.
2 HOW IT WAS WEAVED · AI + HUMAN
Human lineage (content, credited): Maurice Herlihy, Nir Shavit and Moran Tzafrir, Hopscotch Hashing, DISC 2008. The design was aimed at concurrency — a bounded neighbourhood means a lookup can be made lock-free, because the region a reader must examine is known in advance — and the sequential bound measured here is a side effect of that goal rather than its point.
AVAN (AI) should be clear about what the failures mean. At 90% load, 28 keys could not be placed at all: the hopping found no candidate that could legally move, so the insert was refused rather than allowed to violate the invariant. That is the correct behaviour and it is the honest cost — hopscotch does not make a full table work, it converts a latency problem into a capacity problem, and a real implementation resizes at that point.
AVAN (AI) should be clear about what the failures mean. At 90% load, 28 keys could not be placed at all: the hopping found no candidate that could legally move, so the insert was refused rather than allowed to violate the invariant. That is the correct behaviour and it is the honest cost — hopscotch does not make a full table work, it converts a latency problem into a capacity problem, and a real implementation resizes at that point.
3 ONE DIMENSION
Distance from home, at four load factors.
4 TWO DIMENSIONS · INTERACTIVE
A slice of the table, with each key linked to the bucket it belongs to.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the table as a ring, with every key tethered to its home.
AVAN’s addition (the inverse-companion): the forward reading is “bound the probe distance and lookups stay fast.” The inverse is that the bound was not achieved, it was relocated. The work of finding a key is now the work of placing it, paid at insert time by hopping entries backwards, and at high load that work grows until it fails outright. Read backwards, hopscotch does not remove the cost of a crowded table — it moves the cost to the writer and the failure to the capacity, which is the right trade only because reads outnumber writes and a refused insert is easier to handle than an unbounded probe.
LIT on a 1,024-slot table with H = 8 at load factors of 50, 70, 85 and 90 percent, every placed key sits within its neighbourhood in all four runs with a worst observed distance from home of 7 - strictly inside H; at 90% load the table still places 893 of 921 keys; and the cost is displacement work, 416 hops in total across the four runs, which is exactly what buys the bound
FIG Human lineage, credited: Maurice Herlihy, Nir Shavit and Moran Tzafrir, 'Hopscotch Hashing', DISC 2008. The design was aimed at CONCURRENCY - a bounded neighbourhood means a lookup can be made lock-free because the region a reader must examine is known in advance - and the sequential bound measured here is a side effect of that goal rather than its point. AVAN is clear about what the failures mean: at 90% load 28 keys could not be placed at all, because the hopping found no candidate that could legally move, so the insert was REFUSED rather than allowed to violate the invariant. That is correct behaviour and the honest cost - hopscotch does not make a full table work, it converts a LATENCY problem into a CAPACITY problem, and a real implementation resizes at that point.
FIG Human lineage, credited: Maurice Herlihy, Nir Shavit and Moran Tzafrir, 'Hopscotch Hashing', DISC 2008. The design was aimed at CONCURRENCY - a bounded neighbourhood means a lookup can be made lock-free because the region a reader must examine is known in advance - and the sequential bound measured here is a side effect of that goal rather than its point. AVAN is clear about what the failures mean: at 90% load 28 keys could not be placed at all, because the hopping found no candidate that could legally move, so the insert was REFUSED rather than allowed to violate the invariant. That is correct behaviour and the honest cost - hopscotch does not make a full table work, it converts a LATENCY problem into a CAPACITY problem, and a real implementation resizes at that point.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN