How to Learn Hopscotch Hashing: Neighborhoods, Displacement, Bitmaps, Load Factors and Concurrent Table Design

Wait, What?

A hash table can keep keys close to their home bucket even when it is almost full.

Hopscotch hashing is an open-addressing method built around a simple but powerful locality rule: each key should live within a small neighbourhood of the bucket where its hash function says it belongs. When a new key lands too far away, the algorithm does not immediately give up or rehash. It tries to move existing keys backward in a sequence of legal hops until the empty slot is brought close enough to the new key’s home bucket.

The result is a data structure that connects hashing, locality, displacement, bitmaps, load-factor behaviour and concurrent design. It is especially useful for learning why practical data structures are often built around memory access patterns, not only asymptotic notation.

Quick Answer

Learn hopscotch hashing in this order: home bucket → neighbourhood invariant → bitmap or metadata → nearby lookup → insertion search → backward displacement → resize condition → deletion → concurrency → cache locality. Do not start with lock-free details. First be able to move an empty slot toward a key’s home bucket by hand without violating any existing key’s neighbourhood.

1. Start With the Hash-Table Job

A hash table maps a key to an initial array position using a hash function. Collisions are unavoidable, so the design must decide where colliding keys go and how lookups find them later.

Linear probing keeps scanning forward until it finds the key or an empty slot. That design is simple and cache-friendly, but long clusters can form. Cuckoo hashing gives each key a small set of possible homes. Hopscotch hashing takes a different route: it keeps a key near one home bucket, but permits carefully controlled movement among nearby slots.

2. The Neighbourhood Is the Core Invariant

Choose a fixed neighbourhood size H. If a key hashes to bucket b, then the key must be stored within a limited distance of b, commonly in positions:

b, b+1, ..., b+H-1

with wraparound or segmented handling depending on the implementation. This neighbourhood bound means lookup does not scan arbitrarily far. The table can keep compact metadata at the home bucket describing which offsets in the neighbourhood currently contain keys that belong there.

3. Why the Bitmap Helps

Suppose H = 8. A home bucket can conceptually store an 8-bit mask. Bit i says whether the slot at offset i contains a key whose home is this bucket.

home bucket b bitmap: 00101001
                       ^ offsets occupied by keys hashing to b

A lookup computes b, examines the bitmap, and checks only marked positions. The metadata transforms the neighbourhood invariant into a compact search index.

4. Lookup Is Intentionally Boring

Good hash-table lookups should be simple. Compute the home bucket, read the neighbourhood metadata, inspect the indicated slots, compare keys, and either return the value or report absence.

This is an important design lesson: hopscotch hashing makes insertion more sophisticated so that lookup remains local. Many professional data structures deliberately move complexity toward writes to improve a critical read path.

5. Insertion Begins Like Linear Probing

To insert a new key, compute its home bucket and scan forward until an empty slot is found. If that empty slot lies inside the home neighbourhood, insertion is easy: place the key there and update the home’s bitmap.

The interesting case occurs when the first empty slot is too far away.

6. Bring the Empty Slot Backward

Assume the empty slot is at position e. Look backward within roughly H positions for an occupied slot whose key can legally move forward into e while still remaining inside its own home neighbourhood. Move that key into e. The old location becomes the new empty slot. Repeat.

while empty_slot is outside new_key_neighbourhood:
    find movable key behind empty_slot
    if none exists:
        resize_or_rehash()
    move movable key into empty_slot
    update its home metadata
    empty_slot = movable_key_old_position

The empty slot appears to hop backward through the table. Existing keys appear to hop forward. That motion gives the technique its name.

7. Work a Tiny Example

Imagine H = 4 and a new key hashes to bucket 10. The first free slot is 16, too far away. If the key in slot 13 hashes to 12, then moving it from 13 to 16 may still keep it within its allowed neighbourhood 12–15 only if the exact indexing rules permit that position; if not, it cannot move. Another key at 14 might hash to 13 and be movable to 16. After that move, slot 14 becomes empty. If 14 lies inside the new key’s neighbourhood 10–13 it still does not, so another legal displacement is needed.

The lesson is not the specific numbers. It is the legality test: never move a resident key merely because there is space; move it only if the destination remains valid for that resident’s home.

8. Insertion Can Fail Before the Table Is Literally Full

A table may contain empty slots yet still fail to bring one into the required neighbourhood. That is a structural failure, not a capacity count failure. The implementation then needs a resize, rehash, larger neighbourhood or another fallback policy.

This is one reason load factor alone does not tell the whole performance story. The arrangement of homes, collisions and movable keys matters.

9. Deletion Is Mostly Metadata Repair

Once the key is found, clear its slot and clear the corresponding neighbourhood bit at its home bucket. Some designs may perform additional compaction, but the conceptual operation is simpler than insertion because deleting a key cannot violate another key’s neighbourhood by itself.

10. Cache Locality Is a First-Class Goal

Modern processors fetch memory in cache lines rather than one logical field at a time. A small neighbourhood means lookup tends to inspect nearby memory. That can be advantageous compared with pointer-heavy chaining, particularly when the table layout, key/value size and metadata fit the hardware well.

Professional evaluation should therefore measure throughput, probes, cache misses, load factor and memory footprint—not only expected O(1) lookup.

11. Compare With Nearby Designs

• Linear probing: simplest locality story, but clustering can produce long probe sequences.
• Robin Hood hashing: evens out probe distances by displacing entries with smaller probe counts.
• Cuckoo hashing: gives keys alternative locations and may trigger eviction chains.
• Hopscotch hashing: keeps each key within a bounded home neighbourhood and moves entries to preserve that invariant.

There is no universal winner. Workload, deletion rate, table occupancy, concurrency and CPU memory behaviour all matter.

12. Concurrency Changes the Problem

The original hopscotch work was explicitly motivated by sequential and concurrent hash maps on multicore systems. Once multiple threads can search, insert, displace and delete simultaneously, the metadata and relocation sequence must be coordinated so readers never observe an impossible intermediate state.

A beginner should first master the sequential invariant. An advanced learner can then study locking, versioning, ordering and lock-free variants. Concurrency is not “the same algorithm with mutexes added”; it creates new correctness obligations.

13. The Neighbourhood Size Is an Engineering Parameter

A larger H gives insertion more flexibility and may sustain higher occupancy, but it increases neighbourhood metadata and potentially the number of candidate positions checked. A smaller H keeps searches very tight but can force resizes sooner.

The right value depends on machine word size, cache layout, key/value representation and workload. A bitmap that fits in one machine word is attractive because membership offsets can be manipulated efficiently.

14. Hash Quality Still Matters

Hopscotch hashing manages collisions; it does not make a poor hash function harmless. If many keys concentrate into the same few home buckets, local neighbourhoods become crowded and displacement opportunities disappear.

Test both friendly and adversarial key distributions. For untrusted inputs, also consider hash-flooding risks and the security properties of the hash function used by the surrounding system.

15. Correctness Checklist

• Every stored key remains inside the allowed neighbourhood of its home bucket.
• Home metadata exactly matches resident positions.
• Displacement updates both the moved key’s slot and its home’s metadata.
• Lookup never depends on stale metadata.
• Resize preserves every key and recomputes positions under the new table geometry.
• Concurrent implementations define what readers may observe during relocation.

16. Common Failure States

• Moving a key into the empty slot without checking its own home distance.
• Updating the data slot but forgetting the corresponding bitmap.
• Assuming an empty slot guarantees insertion can succeed.
• Confusing neighbourhood size with linear-probe limit.
• Benchmarking only at low occupancy.
• Claiming constant-time worst-case insertion.
• Jumping to lock-free code before understanding the sequential invariant.

17. Practice Ladder: Beginner to Professional

• Beginner: draw a 16-slot table, choose H = 4, and mark each key’s home and legal neighbourhood.
• Foundation: perform insertions manually and update one bitmap per home bucket.
• Intermediate: implement backward empty-slot relocation and verify the invariant after every move.
• Advanced: measure successful/failed displacement lengths across increasing load factors.
• Professional: compare hopscotch, Robin Hood and linear probing under read-heavy, write-heavy and concurrent workloads while recording cache behaviour and tail latency.
• Transfer: explain why shifting complexity into insertion can improve the lookup path.

18. A Better Way to Study the Algorithm

For learners, a useful sequence is trace → label the invariant → predict the next legal move → implement → deliberately break the metadata → write tests that catch the break. This follows programming-education evidence supporting worked examples, subgoal labelling, code tracing and active visualisation rather than passive reading of finished code.

Learning Hall Boundary

This article owns hopscotch hashing as a locality-preserving open-addressing method. It does not replace the existing modern open-addressing overview, minimal perfect hashing, general hash-table foundations, concurrency instruction or MindOS learning-process material. Those remain separate canonical jobs.

Evidence Boundary

Maurice Herlihy, Nir Shavit and Moran Tzafrir introduced Hopscotch Hashing at DISC 2008, describing a resizable sequential and concurrent hash-map family using neighbourhood-based probing and displacement: Tel Aviv University research record, DOI 10.1007/978-3-540-87779-0_24. Later work by Kelly, Pearlmutter and Maguire developed a lock-free variant and analysed its cache locality and scalability: SIAM APOCS — Lock-Free Hopscotch Hashing. The learning sequence also draws on computing-education research showing benefits from subgoal-labelled worked examples and structured tracing.

Professional rule: you understand hopscotch hashing when you can explain the neighbourhood invariant, perform a legal displacement chain by hand, prove that lookup checks the right positions, and benchmark the design under realistic occupancy rather than judging it from average-case notation alone.