The site's Robin Hood hashing page keeps
one table and one hash function, and trades away a hard worst-case bound on get for a
low-variance one: probe lengths cluster tightly near the average, but a pathological input can
still build one long chain. Its cuckoo hashing
neighbor buys a genuine worst-case bound — get checks exactly two fixed slots, always
— but needs two tables and two independent hash functions to do it. Hopscotch hashing asks
whether a hard bound is possible with only one table and one hash function, and answers yes: every
key is guaranteed to live within a fixed neighborhood of its own home slot — the
next H slots starting there, H a small constant chosen when the table is
built. A hop-info bitmap, one per home slot, records exactly which of those
H offsets are occupied by an entry belonging to that home. get never
probes forward hoping to get lucky; it reads the home's own H-bit bitmap and checks
only the offsets it says are occupied — a real O(1) worst case, using one table.
The trick is entirely on the put side. Inserting a key finds the nearest empty slot
by ordinary forward linear probing from its home, exactly like plain linear probing would — but if
that empty slot lands further than H-1 away, it's too far to use directly. Hopscotch
hashing doesn't give up or fall back to scanning; it hops the empty slot closer: it
looks at the H-1 slots immediately behind the empty one, finds an entry there whose own
home is close enough that moving it into the empty slot would still land it inside its own
neighborhood, and moves it — vacating a slot nearer to the original key's home. Repeat until the
empty slot is finally within reach, then place the key and set one bit. No entry ever ends up
outside its own home's neighborhood, which is exactly what makes the bitmap-only get
above safe to trust.
Put a key/value pair, get one back, or delete it. The log traces every slot the operation
touches. The sample loads five keys — cat, pig, fox,
ram, lark — into an 8-slot table with a neighborhood size of 4, in that
order, chosen because it forces a real hop: cat and pig both hash home to
slot 6, so pig takes slot 7. fox hashes home to slot 7 and, finding it
taken, wraps around to slot 0. ram hashes home to slot 6 again and lands at slot 1
(three slots forward, still within reach). By the time lark arrives — home slot 6 once
more — slots 6, 7, 0, and 1 are all occupied, so the nearest empty slot is 2, a distance of 4 from
home 6: too far for a neighborhood of size 4. Hopscotch hashing doesn't stop there: it notices
fox, sitting at slot 0, belongs to home 7 and is close enough to slot 2 to move there
without leaving home 7's own neighborhood, hops it over, and lark takes the
now-vacant slot 0. Click "Reload sample" and watch the log narrate exactly that hop. Then get
fox — the log shows the bitmap-bounded lookup checking a single offset and finding it
immediately, even though fox now sits two slots away from where it first landed.
Finally, uncheck Hop-back displacement and reload: lark gets placed at
the far slot anyway, with no bit set to mark it — get lark and watch it come back "not
found" even though it's sitting right there in the table.
O(k) for a key
of length k.home's hop bitmap and check only the offsets it
marks as occupied, stopping the instant one holds a matching key. At most H checks,
ever, regardless of how much churn the table has been through — O(1) worst case, not
average.get. A new key linear-probes forward from home to find the
nearest empty slot; if it's within H-1, place it there directly. If not, repeatedly
hop the empty slot backward — scan the H-1 slots behind it for an entry that can
legally move into it without leaving that entry's own neighborhood, move it, and treat its
old slot as the new empty one — until the empty slot finally lands within reach of home.
If no legal hop exists anywhere along the way, the table is too full in the wrong place; resize
and retry. O(1) amortized.get, then clear
the slot and its bit. No backward-shift step is needed the way
Robin Hood hashing requires — clearing a bit
can never strand a different key, since every other key's own bit still points straight at its own
slot.class HopscotchHashTable {
#size;
#H;
#table;
#hop;
#count = 0;
constructor(size = 8, H = 4) {
this.#size = size;
this.#H = H;
this.#table = new Array(size).fill(null);
this.#hop = new Array(size).fill(0);
}
#hash(key, size = this.#size) {
let h = 0;
const s = String(key);
for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
return h % size;
}
get(key) {
const home = this.#hash(key);
for (let k = 0; k < this.#H; k++) {
if (!((this.#hop[home] >> k) & 1)) continue;
const idx = (home + k) % this.#size;
const slot = this.#table[idx];
if (slot && slot.key === key) return slot.value;
}
return undefined;
}
has(key) { return this.get(key) !== undefined; }
put(key, value) {
const home = this.#hash(key);
for (let k = 0; k < this.#H; k++) {
if (!((this.#hop[home] >> k) & 1)) continue;
const idx = (home + k) % this.#size;
if (this.#table[idx] && this.#table[idx].key === key) { this.#table[idx].value = value; return; }
}
while (!this.#insertNew(key, value, this.#hash(key))) {
this.#resize();
}
if (this.#count / this.#size > 0.75) this.#resize();
}
// Places a brand-new key. Returns false if no legal slot exists at this
// table size — caller must grow and retry.
#insertNew(key, value, home) {
let free = -1;
for (let step = 0; step < this.#size; step++) {
const idx = (home + step) % this.#size;
if (!this.#table[idx]) { free = idx; break; }
}
if (free === -1) return false;
let dist = (free - home + this.#size) % this.#size;
while (dist >= this.#H) {
let moved = false;
for (let d = this.#H - 1; d >= 1 && !moved; d--) {
const base = (free - d + this.#size) % this.#size;
for (let o = 0; o < d; o++) {
if (!((this.#hop[base] >> o) & 1)) continue;
const y = (base + o) % this.#size;
this.#table[free] = this.#table[y];
this.#table[y] = null;
this.#hop[base] &= ~(1 << o);
this.#hop[base] |= (1 << d);
free = y;
moved = true;
break;
}
}
if (!moved) return false;
dist = (free - home + this.#size) % this.#size;
}
this.#table[free] = { key, value };
this.#hop[home] |= (1 << dist);
this.#count++;
return true;
}
#resize() {
const old = this.#table.filter(Boolean);
let size = this.#size;
let placed;
do {
size *= 2;
this.#size = size;
this.#table = new Array(size).fill(null);
this.#hop = new Array(size).fill(0);
this.#count = 0;
placed = true;
for (const slot of old) {
if (!this.#insertNew(slot.key, slot.value, this.#hash(slot.key))) { placed = false; break; }
}
} while (!placed);
}
delete(key) {
const home = this.#hash(key);
for (let k = 0; k < this.#H; k++) {
if (!((this.#hop[home] >> k) & 1)) continue;
const idx = (home + k) % this.#size;
if (this.#table[idx] && this.#table[idx].key === key) {
this.#table[idx] = null;
this.#hop[home] &= ~(1 << k);
this.#count--;
return true;
}
}
return false;
}
}Every index arithmetic expression wraps with (... + this.#size) % this.#size, not
plain % — the wraparound the first Pitfall below covers. Verified against a plain-
Map reference model over 4,000 randomized trials (300-800 interleaved put/get/delete
calls each, key spaces of 5-20 words, table size 8 with H=4, forcing frequent
collisions, hops, and resizes), checking every get/delete result and the
live entry count against the model after every single call, plus a full sweep of every model key
at the end of each trial — see /tmp/hopscotch_ref.js, scratch, not committed. This
caught a real bug before it shipped: the first draft's put called
#resize() once after a failed #insertNew and tried again exactly once,
without checking whether that second attempt succeeded either — under heavy same-home clustering a
single doubling isn't always enough, and the key being inserted was silently dropped the moment it
wasn't, showing up in the harness as the live count falling one short of the model's. The fix
replaces the one-shot retry with the while loop above, which keeps doubling until
#insertNew actually succeeds. Separately confirmed the page's own five-key walkthrough
by hand against this exact class: cat/pig/fox/ram
land directly, and lark's insert hops fox from slot 0 to slot 2 before
landing in the vacated slot 0 — byte for byte what the demo above shows.
Skipping the hop-back dance doesn't corrupt anything loudly — it just makes a key that's
physically present permanently invisible to a correct, bitmap-bounded get.
Inserting cat, pig, fox, ram, lark
into an empty 8-slot table with the hop-back rule off — placing each key at the first empty
slot linear probing finds, with no window check — lands every key exactly where the rule-on
version does, except lark: instead of triggering a hop, it's placed directly at slot 2,
a distance of 4 from home slot 6, one slot outside the 4-wide neighborhood. Because that distance
doesn't fit in the 4-bit hop map, no bit gets set for it. Calling the real, unmodified
get("lark") against this exact table checks home 6's bitmap, finds no bit that reaches
slot 2, and reports "not found" — while lark is sitting in the table the whole time,
one slot past the boundary get is willing to look at. Checked by running both the
correct and the hop-back-disabled insert sequence against the same reference implementation and
diffing the two resulting tables directly, not by reasoning about it.
Dropping the + this.#size from a wraparound subtraction doesn't crash — it
quietly turns a negative array index into a phantom slot that's never occupied, and the table pays
for it with unnecessary resizes. JavaScript's % keeps the sign of its left
operand, so (free - d) % this.#size without the + this.#size correction
returns a small negative number whenever d exceeds free — exactly the
case the wraparound in this page's own walkthrough hits, since lark's insert needs a
candidate base behind slot 2 in a table indexed 0-7. Running that exact broken subtraction against
the same five-key sequence: this.#hop[-1] reads undefined, which
bitwise-AND coerces to 0, so every candidate check in the wraparound region silently reports "no bit
set here" even where a real, legal hop exists. #insertNew then correctly returns
false — no crash, no wrong answer, just a spurious failure — and put's
retry loop doubles the table and tries again. Rerunning the identical sequence against this broken
version resizes the table from 8 slots to 16 to fit just five entries (31% load factor) where the
correct version needs no resize at all. The bug never touches a value or drops a key; it just makes
the table give up on a hop that was there all along.
A full neighborhood can force a resize far below the usual 0.75 load factor, and that's
correct, not a tuning failure. Inserting hog, cod,
kiwi, crab — four keys that all hash home to slot 0 — fills every offset
0-3 of home 0's neighborhood exactly, one key per offset. A fifth same-home key,
snake, finds the nearest empty slot at distance 4 and needs a hop — but every
candidate base in reach (slots 1, 2, 3) has never held an entry of its own, so their hop bitmaps are
all zero: there is nothing anywhere in range that snake could legally displace. Running
this exact five-key sequence against the reference implementation resizes the table from 8 slots to
16 the moment snake is inserted — with only 5 of the original 8 slots filled, a 62.5%
load factor, well under the 0.75 threshold that would normally trigger a resize. This isn't a bug:
no amount of clever hopping can rescue an insert when
every neighbor in reach is a stranger to the neighborhood, and giving up early to resize is the
correct response, not a sign H=4 was tuned wrong for this specific pathological input.
tessil/hopscotch-map, a real header-only C++ library named
directly after this algorithm — a drop-in alternative to std::unordered_map,
by the same author as the robin_hood::unordered_map-adjacent
tessil/robin-map library the site's own Robin Hood hashing page cites, aimed at the
identical goal: a hard bound on lookup cost without cuckoo hashing's second table.H consecutive array entries — often chosen to match a machine word
(32 or 64) so the whole neighborhood's occupancy fits in one bitmap read — which keeps a lookup's
memory access pattern tight and cache-friendly in a way an unbounded Robin Hood probe chain or a
chaining table's pointer-chasing linked list can't guarantee.Time: get and delete are O(1)
worst case, not just average — a real distinction from
Robin Hood hashing's low-variance-but-
unbounded guarantee, matching cuckoo hashing's
hard bound while needing only one table and one hash function. The bound comes from H
being a small constant fixed at construction time, not from anything about the keys stored.
put is O(1) amortized: most inserts land directly or after a short hop
chain of at most H-1 moves, and resizing (triggered by either the usual 0.75 load
factor or a full neighborhood with no legal hop, see Pitfalls) amortizes to O(1) per
insert over a run, the same way it does for the site's other open-addressing tables.
Space: O(n), one table plus one small bitmap per slot — no second
table's worth of overhead the way cuckoo hashing carries. The real cost of the hard bound isn't
memory, it's insert-side complexity and a resize trigger cuckoo hashing and Robin Hood hashing don't
share: a neighborhood can run out of room well before the table itself does, which is why choosing
H is a genuine tuning knob — small enough to keep each lookup's bitmap read cheap,
large enough that same-home clustering doesn't force resizes far ahead of schedule.
This is one of four collision-resolution strategies the site covers for the same put/get/delete contract — the site's chaining hash table, cuckoo hashing, and Robin Hood hashing are the other three. See Choosing a Hash Table Collision Strategy for the full four-way comparison.