Hopscotch Hashing: Make the Free Slot Hop Back

Hash tables are built around a simple idea: transform a key into an array position, then use that position to find the associated value quickly. A hash function maps a key to a numerical hash value, and the table converts that value into a bucket index. With a suitable table size, a well-distributed hash function, and a controlled load factor, lookup, insertion, and deletion are usually expected to take constant time.

Hopscotch hashing is an open-addressed hashing technique designed to make that constant-time behavior more predictable in practice. Its central idea is to give every bucket a fixed neighborhood near its home position. An item may be stored in one of those nearby positions, and a bitmap records which nearby positions currently belong to the bucket. When an insertion encounters a free slot farther away, the algorithm attempts to move existing entries so that the free slot hops back into the neighborhood of the item being inserted.

The key ideas are fixed neighborhoods, bitmaps, and hopping relocations. Those ideas become easier to understand after reviewing the common foundations of hashing, collisions, load factor, and open addressing.

1. From a key to a bucket​

Suppose a table has $m$ buckets and a key $k$. A hash function produces a hash value $h(k)$. The table then maps that value into the valid bucket range, often using a remainder operation:

The result is called the key's home bucket. For example, if a table has $m=10$ buckets and a key hashes to $47$, then:

The key initially belongs to bucket $7$. A hash map can associate that key with a value, while a hash set can store only the key itself. The physical location of an entry may differ from its home bucket when a collision-resolution method is used, but the home bucket remains important because it tells the search where to begin.

A hash function does not need to produce a unique result for every key. Collisions are unavoidable whenever the number of possible keys is larger than the number of buckets. Two distinct keys can have the same home bucket:

Both keys map to bucket $7$, so the table needs a collision-resolution strategy.

2. Hash maps, hash sets, and expected constant time​

A hash map stores pairs such as a key and a value. A lookup computes the key's home bucket and examines the locations that might contain that key. An insertion computes the same starting point and places the new pair according to the table's collision rules. Deletion removes or marks the pair so that future searches remain correct.

A hash set uses the same basic machinery but cares primarily about membership. To insert a key, the set checks whether the key is already present. To test membership, it searches for the key. To delete a key, it removes the matching entry.

Under favorable conditions, these operations have expected complexity $O(1)$. The word “expected” matters. It describes typical behavior when keys are distributed well and the table keeps its load factor under control. It does not mean that every lookup always performs exactly one operation or that the worst case is always constant time.

If a table contains $n$ entries and has $m$ available bucket positions, its load factor is:

For example, if $7$ entries occupy a table with $10$ positions, then:

As $\alpha$ increases, collisions and occupied search paths generally become more common. A table usually resizes before it becomes too full. Resizing creates a larger array and rehashes the existing keys because their bucket indices depend on the new table size.

Hashing is therefore not magic. Its performance depends on several interacting assumptions: the hash function should distribute keys adequately, the table should retain enough free capacity, and the collision-resolution policy must preserve a reliable way to find displaced entries.

3. Collision resolution by chaining​

Chaining keeps a collection of entries at each bucket. The bucket might point to a linked list, a dynamic array, or another collection. If two keys have home bucket $7$, both can be stored in the collection attached to bucket $7$.

For example, consider a table with ten buckets and keys whose hash values produce the following home buckets:

key A -> 7
key B -> 7
key C -> 2

A chained table can look conceptually like this:

bucket 2: [key C]
bucket 7: [key A, key B]

A lookup for key B computes bucket 7, then searches the entries in that bucket. If the collection is short, this is fast. With a good hash function and a reasonable load factor, the average chain length is controlled, leading to expected $O(1)$ lookup, insertion, and deletion.

The worst case occurs when many keys land in the same bucket. Then one chain may contain $n$ entries, and a search can take $O(n)$. This can happen because of an unfavorable hash function, adversarial input, or simply a poor distribution of keys. Chaining also uses additional space for references or collection objects, although it does not require every entry to occupy a nearby array slot.

Hopscotch hashing does not use this separate per-bucket collection. It is an open-addressed technique: entries live directly in the table array, and collision resolution searches for alternative array positions.

4. Open addressing​

In open addressing, the table itself holds entries. When the home bucket is occupied, the algorithm examines other positions according to a probe rule. A lookup follows the same rule, stopping when it finds the target key or reaches a position that proves the key is absent.

The advantage is that entries are stored in one table array. This can reduce indirection and can make memory access more regular. The cost is that the table must preserve search information carefully. Deletion is especially important because simply clearing a slot can make a later lookup stop too early.

Different open-addressing methods define different probe sequences. Three useful examples are linear probing, double hashing, and Hopscotch hashing.

5. Linear probing​

Linear probing checks consecutive positions. If the home bucket is $b$, the first positions might be:

with indices wrapped around the end of the table. For a table of size $10$, a key whose home bucket is $8$ might probe buckets $8$, $9$, $0$, and then $1$.

Suppose the table contains these entries:

bucket 3: key A
bucket 4: key B
bucket 5: empty

If a new key hashes to bucket 3, the algorithm checks bucket 3, then 4, and places the key in bucket 5. The key is not at its home position, but a lookup for it repeats the same sequence and finds it.

Linear probing is simple and often benefits from nearby memory accesses. However, it can produce primary clustering: once a consecutive run forms, later colliding keys tend to extend that same run. As the load factor rises, probe sequences can become longer. Average performance is commonly described as expected $O(1)$ when the load factor remains suitably bounded, while a worst-case operation can take $O(n)$.

Deletion requires care. If bucket 4 in the example is cleared completely, a lookup that starts at bucket 3 might see bucket 4 as empty and incorrectly conclude that the key formerly stored at bucket 5 is absent. Implementations commonly use a tombstone state or relocate entries to preserve the probe sequence. The exact deletion policy is an implementation detail, but the correctness requirement is general: deletion must not break the path used to find entries that were displaced.

6. Double hashing​

Double hashing uses a second hash-derived step size. Instead of checking every consecutive position, the probe sequence can be written as:

where $h_1(k)$ gives the initial position, $h_2(k)$ gives the step size, and $i$ is the probe number. For example, with $m=11$, $h_1(k)=3$, and $h_2(k)=4$, the first positions are:

Double hashing can spread probes more broadly than linear probing and reduce primary clustering. The second step must be selected so that the sequence can reach the relevant table positions; otherwise, the probe may visit only a subset of the table.

Like other open-addressed methods, double hashing relies on a controlled load factor. It can provide expected $O(1)$ operations under suitable conditions, but a long probe sequence can make an individual operation take $O(n)$ in the worst case. Resizing and rehashing are therefore important parts of practical operation.

7. The central idea of Hopscotch hashing​

Hopscotch hashing combines open addressing with a local neighborhood rule. Each home bucket has a fixed neighborhood of nearby positions. An entry whose home bucket is $b$ is intended to reside within that neighborhood rather than arbitrarily far away.

Let the neighborhood size be $H$. A simple conceptual neighborhood for bucket $b$ consists of positions:

Indices may wrap around the table boundary. The exact representation and boundary details depend on the implementation, but the important rule is local: an entry must remain within a bounded distance of its home bucket.

This fixed neighborhood changes how lookup works. Instead of scanning an unbounded sequence of positions, a lookup examines the neighborhood associated with the key's home bucket. The table can record which positions in that neighborhood contain entries belonging to the home bucket.

The bitmap is central to this design. A bitmap gives one bit to each neighborhood offset. If bit $j$ is set, the table records that an entry whose home bucket is $b$ currently occupies position $b+j$. If the bit is clear, no entry belonging to $b$ occupies that offset.

For a neighborhood of size $8$, a bitmap might be shown as:

offset:  0 1 2 3 4 5 6 7
bitmap:  1 0 1 0 0 1 0 0

This means that entries belonging to the home bucket occupy offsets $0$, $2$, and $5$. A lookup for a particular key first computes its home bucket, reads the bitmap, and checks only those indicated positions for the key. It does not need to compare the key with every position in a broad table-wide probe sequence.

The bitmap does not replace key comparison. A set or map still needs to compare the searched key with candidate entries. Instead, the bitmap identifies which nearby slots are candidates for that home bucket.

8. A small Hopscotch example​

Assume a table with positions numbered from 0 through 9, and a neighborhood size of $H=4$. Suppose key A hashes to home bucket 3. Its allowed neighborhood is conceptually:

positions 3, 4, 5, 6

If A is stored at position 5, the bitmap for home bucket 3 sets the bit for offset $2$ because:

The relevant record can be represented conceptually as:

home bucket: 3
bitmap:      0010
entry:       key A at position 5

The visual ordering of bitmap bits depends on convention; the important fact is that one bit corresponds to offset $2$.

Now suppose a second key, B, also hashes to bucket 3. If position 3 is occupied and position 4 is available, B can be placed at 4, which is still inside the neighborhood. The bitmap then records offsets $1$ and $2`.

home bucket: 3
occupied offsets: 1, 2

A lookup for B computes home bucket 3, checks the bitmap, and examines positions 4 and 5 rather than scanning unrelated positions.

The useful property is not that every entry stays at its exact home bucket. Collisions still occur. The useful property is that the displaced entries remain within a known, fixed neighborhood of their home bucket.

9. Why hopping relocations are needed​

The difficult case occurs when an insertion finds a free slot, but that free slot lies outside the new key's neighborhood. A simple open-addressed table might place the key there and make future searches travel farther. Hopscotch hashing instead attempts a relocation.

Assume the new key has home bucket 3, neighborhood size $H=4$, and therefore needs a position among 3, 4, 5, or 6. Suppose those positions are full, but position 8 is free.

position:  3 4 5 6 7 8
state:     X X X X X .

The free slot at 8 is too far away. The algorithm looks for an entry in an earlier position that can be moved to the free slot while still remaining within that entry's own neighborhood. If an entry at position 6 belongs to home bucket 5, then moving it to position 8 may be valid when position 8 is still inside the neighborhood of bucket 5.

After moving that entry, position 6 becomes free. The free slot has effectively hopped backward from 8 to 6, closer to the new key's home bucket.

before:   position 6 contains old entry, position 8 is empty
move:     old entry 6 -> 8
after:    position 6 is empty, position 8 contains old entry

The algorithm may repeat this process. Each valid relocation moves an existing entry into the current free position and creates a new free position closer to the desired neighborhood. When the free position enters the new key's neighborhood, the new key can be inserted there.

This is the meaning behind “make the free slot hop back.” The free slot is not moved directly. Existing entries are relocated so that the empty location moves toward the home bucket that needs it.

Every relocation must preserve the displaced entry's own neighborhood condition. It is not enough to move an entry to any empty slot. The move is useful only if the entry remains discoverable from its home bucket, and the associated bitmap must be updated consistently.

10. Updating the bitmap during a relocation​

Suppose an entry belonging to home bucket $b$ moves from offset $r$ to offset $s$. The bitmap for $b$ must clear bit $r$ and set bit $s$.

If the old location is position 6, the new location is position 8, and the home bucket is position 5, then:

The record for home bucket 5 changes from indicating offset 1 to indicating offset 3. The entry's key and value move in the table, but the bitmap is what tells future lookups where to search.

For the key being inserted, the algorithm sets the bit corresponding to its final offset. For every relocated entry, it changes that entry's home-bucket bitmap. A correct implementation must keep the table slots, ownership information, and bitmaps synchronized. If one is changed without the others, lookup can miss an existing key or inspect a slot that does not belong to the home bucket.

11. Lookup in Hopscotch hashing​

A Hopscotch lookup can be described in conceptual steps:

1. Compute the key's hash value.
2. Convert it to the home bucket.
3. Read the home bucket's neighborhood bitmap.
4. Use the set bits to identify candidate positions.
5. Compare the searched key with the entries at those positions.
6. Report the matching value or conclude that the key is absent.

The fixed neighborhood bounds the number of candidate offsets by $H$. If $H$ is treated as a fixed constant, the neighborhood portion of a lookup is bounded by a constant-sized scan. This is the source of the stable open-addressed lookup described by Hopscotch hashing.

It is important to distinguish a design goal from an unconditional mathematical guarantee. A fixed neighborhood can bound the intended local search, but insertion may fail if no valid relocation sequence can bring a free slot into the needed neighborhood. Practical implementations address this by resizing, changing capacity, or using another policy when the neighborhood cannot be maintained. The exact response is implementation-dependent.

A lookup also needs to distinguish an empty position from an occupied position and compare the actual key. The bitmap narrows the candidate set, but it does not eliminate the possibility that several different keys belong to the same home bucket. Hash values are not identities; key equality remains the final test.

12. Insertion and the load factor​

A conceptual Hopscotch insertion has these stages:

1. Compute the home bucket for the new key.
2. Check the neighborhood for an existing equal key if the structure is a map or set that rejects duplicates.
3. Search for a free slot somewhere in the table.
4. If the free slot is outside the target neighborhood, attempt hopping relocations.
5. Insert the new entry once the free slot is inside the neighborhood.
6. Set the appropriate bitmap bit.

The load factor remains important. Let $n$ be the number of stored entries and $m$ the number of table positions. Then $\alpha=n/m$. A high $\alpha$ means fewer free slots are available for relocation. Even if a free slot exists, it may be difficult to move it into a particular neighborhood without violating other entries' constraints.

A resize increases $m$, creates more empty positions, and usually rehashes all entries. Rehashing is necessary because the home bucket depends on the table capacity:

If $m$ changes, the result can change. An entry that belonged to bucket 3 in a table of size 10 may belong to another bucket after the table grows. The new table must rebuild its neighborhoods and bitmaps rather than copying entries blindly to the same indices.

A resize operation can take $O(n)$ because it processes all stored entries. However, if resizing happens occasionally and the capacity grows sufficiently, the cost can be amortized across many insertions. Individual insertion still has a possible relocation cost, and the worst-case behavior depends on the implementation and the state of the table.

The load factor is not the only consideration. Neighborhood size also affects behavior. A larger neighborhood gives the insertion process more nearby positions in which to place an entry, but it increases the amount of metadata and the number of candidate offsets that a lookup may inspect. A smaller neighborhood limits lookup work but can make valid placement harder as the table becomes crowded. The appropriate choice is an engineering trade-off rather than a universal constant supplied by the hashing idea itself.

13. Deletion considerations​

Deletion in an open-addressed structure must preserve future search correctness. In Hopscotch hashing, the bitmap gives an explicit record of which nearby positions belong to a home bucket. Removing an entry therefore requires clearing the corresponding bitmap bit and making the table slot available according to the implementation's rules.

A deletion may create a hole inside a neighborhood. That is not necessarily a problem: the bitmap can show that the offset is no longer occupied by an entry belonging to that home bucket. The important requirement is that other entries remain discoverable and that a newly available slot can be used safely by later insertions.

Some implementations may use additional metadata or relocation rules during deletion. The central principles are to update all metadata that participates in lookup and to avoid creating a state in which a valid entry is hidden from its home bucket.

Deletion can also interact with duplicate handling. If a map updates the value for an existing key, it should not create a second entry. If a set rejects duplicates, the membership check must occur before insertion. In both cases, the bitmap must describe the actual occupied entries rather than merely recording that a home bucket has been used at some point in the past.

14. Complexity and worst-case behavior​

For hash maps and hash sets, expected lookup, insertion, and deletion are commonly written as $O(1)$ when the hash function distributes keys well and the load factor is controlled. A resize or full rehash can take $O(n)$. A poorly distributed hash function, excessive occupancy, or an unfavorable collision pattern can cause an individual operation to take $O(n)$ in the worst case.

Hopscotch hashing aims to keep lookups local by maintaining a bounded neighborhood. If the neighborhood size $H$ is fixed, examining the bitmap and its candidate positions is constant with respect to $n$. Relocation work during insertion can still vary. If many entries must be moved, the insertion may take longer, and if no valid sequence can be found, the implementation must use a failure or resize policy.

A useful summary is:

• Expected lookup: $O(1)$ under suitable distribution and load conditions.
• Expected insertion: $O(1)$ in the usual amortized or average-case discussion, with relocation work included.
• Expected deletion: $O(1)$ when metadata updates are local.
• Resize or rehash: $O(n)$ for $n$ existing entries.
• Worst-case hash-table operation: potentially $O(n)$ without stronger assumptions.
• Space: typically $O(m)$ for a table with $m$ positions, plus metadata such as bitmaps.

These expressions describe the standard complexity model rather than a guarantee that every implementation has identical constants or behavior. A fixed neighborhood makes the lookup path more controlled, but it does not remove the need for a capacity policy or eliminate every possible insertion difficulty.

15. Hashing compared with sorting and balanced trees​

Hashing is attractive when the main operation is exact-key lookup. A hash map can associate an identifier with a count, object, or cached result without maintaining the keys in sorted order. A hash set can answer membership questions without sorting a separate list.

Sorting has different strengths. Sorting $n$ items typically takes $O(n\log n)$ time with comparison-based methods, after which binary search can find an item in $O(\log n)$ time. Sorted data also supports ordered traversal, range queries, predecessor and successor operations, and other order-based tasks that ordinary hashing does not naturally provide.

Balanced search trees maintain order while offering lookup, insertion, and deletion in $O(\log n)$ worst-case time under their balancing rules. They are useful when predictable logarithmic bounds and ordered operations matter more than expected constant-time exact lookup.

Hashing usually offers expected $O(1)$ exact-key operations but does not inherently answer questions such as “which keys lie between $a$ and $b$?” A balanced tree can answer such questions naturally. Hopscotch hashing retains the general unordered nature of hash tables while focusing on stable local lookup behavior inside an open-addressed array.

There is also a space and implementation trade-off. A chained table may need references and separate collections, while an open-addressed table reserves array positions and metadata. Sorting may use a separate ordered representation or rearrange the input. A tree stores balancing and link information. The best structure depends on whether the workload emphasizes exact membership, ordered access, memory locality, predictable worst-case bounds, or simple implementation.

16. Practical uses​

Frequency counting​

Frequency counting stores a number as the value associated with each key. For every input item, a map lookup finds its current count, and insertion or update increments it. A hash map is appropriate because the program needs exact-key access rather than sorted order.

The conceptual operation is:

for each item:
    count[item] = count[item] + 1

A Hopscotch-based map can keep the entry and its lookup metadata in the table array while using the item's home bucket and neighborhood bitmap to find it. The total work for $n$ input items is commonly expected $O(n)$ when each map operation is expected $O(1)$.

Deduplication​

A hash set can record which items have already appeared. For each new item, membership is checked; if the item is absent, it is added. This supports the common pattern of removing duplicates or detecting repeated identifiers.

for each item:
    if item is not in seen:
        add item to seen

The set does not need a value for each key, so its table entries can be conceptually simpler than map entries, although the collision and neighborhood mechanisms still apply. The final result is not automatically sorted; if sorted unique output is required, sorting or an ordered structure may be added as a separate step.

Two-sum-style lookups​

In a two-sum-style problem, a program processes values and asks whether a complementary value has already been seen. If the current value is $x$ and the target is $T$, the needed complement is:

A hash set can test whether that complement is present in expected $O(1)$ time per item. Processing $n$ items therefore commonly leads to expected $O(n)$ total time, compared with a possible $O(n\log n)$ approach based on sorting. The choice depends on whether the task needs original positions, ordered output, memory constraints, or exact worst-case guarantees.

For a map variant, the value stored for each number can be its index or a count. The collision-resolution policy is invisible to the algorithm using the map, but it determines how efficiently each complement lookup is performed.

Grouping​

Grouping uses a map from a group key to a collection of members. For example, records can be grouped by a category, identifier, or computed signature. The map locates the appropriate group, and the record is appended there.

groups[group_key].append(record)

The grouping key's home bucket, neighborhood, and bitmap determine how quickly the map locates the group entry. The collections stored as values may grow independently; hashing locates the group, while the chosen collection manages that group's members.

Caching​

A cache maps a request key to a stored result. A lookup checks whether a result is already present. On a miss, the result is computed and inserted. Exact-key lookup is the central operation, so a hash map is a natural representation.

A cache also introduces capacity and eviction policy questions. Hashing determines how entries are found, while eviction determines which entries are removed when capacity is reached. These are separate concerns. Hopscotch hashing can organize the table's occupied entries, but the hashing technique does not define a particular eviction strategy.

When a cache grows or shrinks, rehashing may be needed because changing the table capacity changes home-bucket calculations. Eviction can create deletions, so the cache's table must also preserve bitmap and neighborhood invariants after removal.

Prefix-sum maps​

Prefix-sum techniques often store previously seen prefix values in a map. Suppose a running prefix value is $P_j$. If a later prefix value is $P_i$ and the desired interval sum is $T$, then an earlier prefix satisfying:

indicates a matching interval under the usual prefix-sum relationship. A map can store counts or indices for earlier prefix values, allowing each new prefix to perform an expected constant-time lookup. This turns many nested-search approaches into expected linear-time scans.

The map may need to retain more than one piece of information. It can store the earliest index, a frequency, or another aggregate value. Hashing still supplies the exact-key access pattern; the stored value determines what the prefix-sum algorithm can reconstruct.

17. Implementation checklist for Hopscotch hashing​

A practical implementation should make several invariants explicit:

1. Every entry has a home bucket determined by the hash function and current capacity.
2. Every entry is physically stored within the allowed neighborhood of that home bucket.
3. The bitmap for each home bucket accurately records the offsets occupied by its entries.
4. Every relocation preserves the moved entry's neighborhood rule.
5. Lookup examines only positions identified by the correct bitmap.
6. Deletion updates both the table slot and the relevant bitmap.
7. Resizing rebuilds home buckets, neighborhoods, and bitmap metadata.
8. Insertion has a defined response when relocation cannot reach a valid slot.

These invariants explain why the bitmap and hopping operations are not optional decorations. The bitmap makes local lookup possible, while hopping relocations help maintain the local placement rule when collisions fill the nearby positions.

Testing should cover ordinary collisions, several keys with the same home bucket, insertion into a partially occupied neighborhood, a relocation chain, deletion followed by reinsertion, and a resize. It should also verify that every key remains findable after an entry moves. A useful debugging representation includes each slot's key, its home bucket, its current offset from home, and the bitmap associated with that home bucket.

The table should also define how empty positions are represented and how a failed insertion is handled. A table that silently places an entry outside its neighborhood may appear to work for some lookups while violating the invariant that makes Hopscotch hashing useful. Clear metadata and explicit consistency checks help prevent that class of error.

18. Final perspective​

Hashing begins with a simple computation: map a key to a home bucket. Collisions make that computation insufficient by itself, so a data structure needs a way to store and find keys that share a bucket. Chaining keeps colliding entries together in a secondary collection. Open addressing keeps entries in the table array and searches alternative positions. Linear probing uses consecutive positions, while double hashing uses a second hash-derived step.

Hopscotch hashing takes a more local approach to open addressing. It assigns each home bucket a fixed neighborhood, records occupied offsets with a bitmap, and uses hopping relocations to move a free slot back toward the neighborhood that needs it. The intended result is a stable, bounded local lookup pattern while retaining the compact array-oriented character of open addressing.

The broader engineering lesson is that expected $O(1)$ hashing depends on more than a single hash calculation. Distribution, load factor, collision policy, deletion rules, metadata, resizing, and worst-case behavior all matter. Hopscotch hashing makes those concerns visible: the neighborhood defines where an entry may live, the bitmap defines where lookup should look, and relocation preserves the invariant when collisions fill the nearby positions.

For exact-key tasks such as frequency counting, deduplication, two-sum-style searches, grouping, caching, and prefix-sum maps, hash-based structures remain powerful because they exchange sorted order for expected constant-time access. When ordered traversal or worst-case logarithmic bounds are more important, sorting or balanced trees may be the better fit. The right choice depends on the operations the application actually needs.