Why are entries moved?

Relocation can bring an empty slot into a new key's allowed neighborhood while preserving existing entries' neighborhood constraints.

What does the bitmap or similar metadata record?

It identifies nearby positions containing entries that belong to a particular home bucket.

Is hopscotch hashing a secure digest algorithm?

No. It is a way to organize a hash table and resolve collisions, distinct from cryptographic hashing.

AI Glossary / Graphs and symbolic AI / Intermediate

Hopscotch hashing

Definition

Hopscotch hashing is a hash-table technique that keeps each stored entry within a small neighborhood of its home bucket. When an insertion finds an empty slot too far away, it relocates suitable existing entries to bring an empty position closer. Neighborhood metadata helps lookups inspect the relevant nearby positions efficiently.

What it means

A hash function chooses an entry's home bucket, but collisions mean that several keys may want the same home. Hopscotch hashing allows those entries to occupy different nearby slots while maintaining a bounded neighborhood rule. The physical storage location can differ from the home bucket.
The technique was introduced by Maurice Herlihy, Nir Shavit, and Moran Tzafrir for sequential and concurrent hash maps. It is a data-structure design, not a cryptographic hash function or a machine-learning algorithm. Its performance should be assessed for a particular implementation and workload rather than inferred from the name.

How it works

For each home bucket, maintain information identifying which offsets in its neighborhood contain entries belonging to that bucket. A lookup computes the home, consults the metadata, and compares keys at the indicated positions. It need not treat every nearby occupied slot as a matching-home candidate.
During insertion, locate an empty slot. If it lies outside the new key's permitted neighborhood, move an existing entry into that slot only when the move preserves that entry's own neighborhood constraint. This creates a nearer empty slot. Repeat as appropriate, then insert and update metadata. If suitable relocation cannot be completed, the implementation needs an appropriate fallback such as resizing.

Three practical examples

A data-structures class traces collisions and relocations in a small table to understand bounded-neighborhood storage.
A systems experiment compares lookup and insertion behavior at several load factors using the same key distribution.
A concurrent-programming study examines how an implementation protects relocation and metadata updates while other threads perform operations.

Think of it this way

Think of residents assigned to a short section of numbered parking spaces near their home. A resident may move to another allowed space to free a suitable position for a newcomer. The analogy is limited because the table follows exact hash and metadata rules, and concurrent changes require synchronization that a parking sketch does not capture.

Worked example

Use a toy table without wraparound in the illustrated region and a neighborhood size of four slots. A key with home bucket 2 must occupy slot 2, 3, 4, or 5. Suppose those slots are occupied, slot 6 is also occupied, and the next empty slot is 7.
Assume the entry currently in slot 5 has home bucket 4. Its permitted neighborhood is slots 4 through 7, so moving that entry from slot 5 to slot 7 preserves its constraint. The move creates an empty slot at 5, which is inside the new key's neighborhood. The new home-2 key can now be stored at slot 5.
The metadata for home 4 must stop pointing to offset 1 and start pointing to offset 3 for the moved entry. The metadata for home 2 must record the new entry at offset 3. A key at slot 5 whose home were 2 could not be moved to slot 7 under these rules, because offset 5 exceeds the allowed range. This original example illustrates one valid relocation, not every insertion case or a full concurrent implementation.

Illustrative case study

In a fictional systems lesson, Spruce Maps implements the sequential toy table and tests lookups after each insertion. One test fails because a relocated entry's data moved correctly but its home bucket's metadata was not updated.
The team adds checks that every stored entry lies within its permitted neighborhood and that metadata agrees with actual locations. It then keeps concurrent behavior as a separate implementation task. The invented case illustrates the importance of maintaining the invariant, without claiming a benchmark advantage or proving thread safety.

Common misconceptions and mistakes

Hopscotch hashing does not remove collisions; it manages them. The home bucket is not necessarily the slot where a key is stored, and moving an entry does not change its hash-derived home.
A bounded lookup neighborhood also does not mean every insertion finishes in a fixed tiny number of steps. Relocation can fail or require resizing. Do not infer that every implementation is lock-free merely because the original work includes concurrent algorithms. Progress guarantees, synchronization, and memory management belong to the specific implementation. Published speedups on historical hardware are not universal promises for current applications.

Business use

The technique is relevant to systems where hash-table behavior affects throughput, memory locality, or concurrent access. It offers a useful design example of spending effort during insertion to keep lookup locations constrained.
Compare complete operations under representative keys, table sizes, load factors, and read/write mixtures. Include resizing costs and unsuccessful lookups where relevant. For concurrent versions, evaluate correctness and progress properties as well as throughput. A suitable table depends on the application's requirements; no single collision-resolution scheme is best for every workload or environment.

Check your understanding

Why is moving the home-4 entry from slot 5 to slot 7 allowed in the worked example?

Answer: With neighborhood size four, its allowed slots are 4, 5, 6, and 7. The move remains within that range and frees slot 5 for the new home-2 entry.

Related terms

Linear probing
hash table
collision resolution
open addressing
home bucket
load factor
cache locality
concurrent data structure

Learn next

Draw the toy table and update the home-bucket metadata after the relocation. Then construct a case where no permitted move brings an empty slot into range. Compare lookup, insertion, and resizing separately when evaluating alternative hash-table designs.

Sources

Sources: Herlihy, Shavit, and Tzafrir, Hopscotch Hashing, author-hosted original paper: https://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf

Previous: Hopfield Network Next: Horizon effect