Hopscotch Hashing: Neighborhood-Bounded Open Addressing

The problem: fast lookups when the table is nearly full

Classic open addressing stores every key in one flat array and resolves collisions by probing other slots. Linear probing is beloved for its sequential memory access — modern CPUs prefetch the next cache line — but it suffers primary clustering: runs of occupied slots merge into long stretches, and expected probe length explodes like O(1/(1-α)²) as the load factor α approaches 1. At α = 0.9 that is dozens of probes.

Cuckoo hashing fixes the worst case — a lookup checks exactly two candidate slots — but those two slots live in different arrays and hit two random cache lines, and inserts can enter displacement loops that force a rehash well below full capacity.

Hopscotch hashing asks: can we keep the two-probe worst-case guarantee of cuckoo while retaining the single-cache-line access of linear probing, even at 90%+ load? Its answer is to require that a key always resides within a fixed-size window — the neighborhood — of its home bucket, and to actively rearrange the table on insert to preserve that invariant.

How it works: the hop bitmap and the hopscotch move

Every bucket i owns a virtual bucket: the range of slots [i, i+H-1]. It also stores an H-bit hop-information bitmap. Bit j being set means "the key in slot i+j hashed to home bucket i." A lookup for key k computes i = hash(k), reads the bitmap, and probes only the slots whose bits are set — never more than H slots, all near each other.

Insertion has two phases:

• Find a free slot by linear probing forward from i until an empty slot e is found.
• Hop the hole home. If e is already within [i, i+H-1], place k there and set the bit. Otherwise the empty slot is too far, so repeatedly displace: find a key in the window ending at e whose home bucket is close enough that moving it into e is legal, move it, and update both bitmaps. This slides the empty slot backward by up to H-1 each step until it lands inside i's neighborhood.

insert(k):
  i = hash(k)
  e = linear_probe_for_empty(i)          // O(1) expected
  while e - i >= H:                       // hole too far
     e = hopscotch_move_hole_closer(e)    // displace a nearer key
     if no legal move: resize_and_rehash()
  table[e] = k; bitmap[i] |= (1 << (e-i))

Complexity and a worked step trace

Lookup: read one bitmap, probe at most H flagged slots — O(1) expected, and the hard cap is H (a constant, e.g. 32), so worst case is O(H) = O(1). Because the neighborhood is contiguous, this is typically a single 64-byte cache-line read. Insert/delete: O(1) expected; a pathological insert may perform up to O(H) displacement hops before succeeding or triggering a resize. Space: one slot array plus H bits per bucket — with H=32 that is one extra 32-bit word per entry.

Worked trace with H=4. Say keys A,B,C all hash home to bucket 2, and slots 2,3,4 fill, but slot 5 is empty and belongs to bucket 2's neighborhood only if 5-2 < 4 — it does (distance 3), so A can go to 5 directly. Now insert D also homing to 2: linear probe finds empty slot 8, but 8-2 = 6 ≥ 4, too far. Hopscotch finds the key in slot 6 whose home is 5, moves it into 8 (legal: 8-5=3), sliding the hole to 6; still 6-2=4, too far, so it moves the key homed at 4 into 6, sliding the hole to 4 — now 4-2=2 < 4, so D lands in slot 4. Bitmaps updated at each hop.

Where it is used in real systems

Hopscotch hashing was designed with multicore concurrency front-of-mind, which is why it shows up in high-throughput, cache-sensitive settings:

• Concurrent hash maps. The original paper's motivation was a lock-based and near-lock-free concurrent table; the neighborhood structure lets threads lock a small window rather than the whole bucket chain. A 2019 follow-up (Kelly, Pearlmutter, Maguire) built a fully lock-free hopscotch table on this base.
• C++ libraries. Tessil's widely used tsl::hopscotch_map / tsl::hopscotch_set implement it as a drop-in std::unordered_map replacement, benchmarked as faster on lookups at high load.
• In-memory database and analytics indexes, join hash tables, and set-membership structures where the table runs hot and dense and every avoided cache miss matters.
• Systems research comparing probing schemes routinely cites hopscotch as the reference point for "bounded-neighborhood open addressing."

Its sweet spot is read-heavy, high-load, cache-bound workloads on machines where a random memory access costs 100+ cycles but a bitmap test is nearly free.

How it compares to the alternatives

All three modern open-addressing schemes attack linear probing's clustering, but they optimize different things:

• vs. Robin Hood hashing: Robin Hood equalizes probe-length variance by having keys with longer probe sequences steal slots from luckier keys; it has excellent average memory efficiency and simpler code, and often wins on update-heavy workloads. Hopscotch instead gives a hard worst-case probe cap of H and slightly better lookup locality — pick hopscotch when tail latency matters, Robin Hood when average cost and simplicity do.
• vs. Cuckoo hashing: Cuckoo guarantees a 2-slot lookup but reads two random cache lines and can thrash on insert near ~50% per-table load. Hopscotch's H slots are contiguous (one cache line) and it sustains α > 0.9.
• vs. Chaining: Chaining never displaces but pays a pointer-chase per probe and poor locality; hopscotch is array-only, so it prefetches beautifully.

The tradeoff hopscotch accepts is implementation complexity: maintaining bitmaps and correctly cascading displacements is fiddlier than any of the above.

Pitfalls, failure modes, and significance

The resize trap. The neighborhood invariant can genuinely fail: if the insert's linear probe finds a free slot but no legal displacement chain can slide a hole into the home neighborhood, the table must resize and rehash — even if it is not literally 100% full. Choosing H too small (e.g. 8) makes this happen sooner; too large (say 64) weakens the single-cache-line benefit. H = 32 (one machine word, one bitwise scan) is the common sweet spot.

Clustering under adversarial hashes. A weak or attacker-chosen hash that piles many keys onto one home bucket will overflow that neighborhood; a good, well-distributed hash (or a seeded one) is essential.

Deletion bookkeeping. Removing a key must clear the correct bit in the home bucket's bitmap, not the slot's — a classic implementation bug — and some variants then pull a distant key back to shorten future probes.

Significance. Hopscotch hashing is a landmark demonstration that clever displacement, not chaining, can deliver constant-bounded probes, single-cache-line access, tolerance of 90%+ load, and concurrency-friendliness all at once — a design lens that influenced later cache-conscious and lock-free table research.

Hopscotch hashing versus its open-addressing cousins

Scheme	Worst-case probe bound	Behavior at high load (α>0.9)	Cache locality
Linear probing	O(1/(1-α)²) expected; unbounded worst	Degrades sharply; long primary clusters	Excellent (sequential) until clustering
Robin Hood hashing	Low variance, no hard cap	Good; minimizes probe-length variance	Good; may scan past unrelated keys
Cuckoo hashing (2 tables)	2 slots guaranteed for lookup	Insert may loop/rehash near ~50% per table	Poor; two random cache lines
Hopscotch hashing	H slots (e.g. 32), one bitmap read	Strong; keeps probes small past 0.9	Excellent; neighborhood ≈ 1 cache line