Hopscotch Hashing, in depth: bounded neighbourhoods, hop bitmaps, backward displacement and concurrent tables

The neighbourhood invariant and the hop bitmap

Let the table have n slots and let home(k) = hash(k) mod n. Hopscotch keeps one invariant: every key k is stored in one of the slots home(k), home(k)+1, ..., home(k)+H-1 (wrapping around the end). H is a small constant, typically 32 or 64, chosen to match a machine word so the bookkeeping fits in one register.

The bookkeeping is the hop bitmap: each bucket b stores an H-bit word in which bit i is set when slot b+i holds a key whose home is b. Neighbourhoods overlap, so slot 7 may hold a key from bucket 5 while bucket 7's own keys sit in slots 8 and 9. The bitmap says exactly which slots to check, so a lookup never inspects a slot that belongs to a different bucket, and a miss is answered without scanning to an empty slot as linear probing must.

Lookup is therefore:

def get(self, key):
    home = self.hash(key) % self.n
    bits = self.hop[home]
    while bits:
        i = (bits & -bits).bit_length() - 1      # index of lowest set bit
        j = (home + i) % self.n
        if self.keys[j] == key:
            return self.vals[j]
        bits &= bits - 1                          # clear that bit
    return None

In C this loop is a count-trailing-zeros instruction per candidate. Implementations that also store a few bits of each key's hash beside it can skip most full key comparisons, which matters when keys are strings.

Insertion: hopping the free slot home

Insertion has two phases. First, probe linearly from home(k) for the first empty slot, at distance d. If d is less than H, put the key there, set bit d of the home bitmap, and stop. Otherwise the empty slot is too far away, and the algorithm moves it backwards, one hop at a time:

1. Call the empty slot free. Look at the H-1 buckets before it, starting with the farthest, free - (H-1).
2. For a candidate bucket b, find a key of b that sits in a slot before free. Because free is within b's neighbourhood, moving that key into free keeps the invariant.
3. Move it, update b's bitmap (clear the old bit, set the new one), and the vacated slot becomes the new free slot, closer to home(k).
4. Repeat until free is within H of home(k), then place the key. If no bucket in range has a movable key, the table cannot satisfy the invariant: resize and retry.

Each hop moves free back by up to H-1 slots, so a few hops cover a long distance. The displaced keys stay close to their homes, which is why lookups remain fast. Compare Robin Hood hashing, which also displaces keys during insertion but keeps clusters contiguous instead of bounded.

A tested implementation

The insertion routine below is the core of a full implementation that also has get, put, delete and resize. Over 30 randomized runs of 3,000 mixed puts, deletes and gets with a deliberately small H = 8, it matched a Python dict after every run and passed an invariant check (every set bit points at a key whose home is that bucket).

def _try_insert(self, home, key, val):
    d = 0                                         # 1. linear probe for a free slot
    while d < self.n and self.keys[(home + d) % self.n] is not None:
        d += 1
    if d == self.n:
        return False
    while d >= self.H:                            # 2. hop the free slot backwards
        free = (home + d) % self.n
        moved = False
        for back in range(self.H - 1, 0, -1):     # candidate bucket b = free - back
            b = (free - back) % self.n
            bits = self.hop[b]
            for i in range(back):                 # b's earliest key before free
                if bits >> i & 1:
                    src = (b + i) % self.n
                    self.keys[free], self.vals[free] = self.keys[src], self.vals[src]
                    self.keys[src] = self.vals[src] = None
                    self.hop[b] = (bits & ~(1 << i)) | (1 << back)
                    d -= back - i
                    moved = True
                    break
            if moved:
                break
        if not moved:
            return False                          # caller resizes
    j = (home + d) % self.n
    self.keys[j], self.vals[j] = key, val
    self.hop[home] |= 1 << d
    return True

The caller, put, first checks the bitmap for an existing key to update in place, then calls this in a loop that doubles the table on failure. That loop needs a cap: if more than H keys share one home bucket, no table size can hold them, so the tested version raises an error after three consecutive resizes instead of growing forever.

Worked example: six keys, H = 4

Take n = 8 and H = 4, with hand-chosen homes A = 1, B = 1, C = 2, D = 3, E = 4. Inserting A to E in order needs no hops: A lands in 1, B probes to 2 (bit 1 of bucket 1), C to 3, D to 4, E to 5. Bucket 1's bitmap reads 1100 (offsets 0 and 1, written lowest bit first).

Now insert F with home 1. The first empty slot is 6, at distance 5, and 5 is not below H = 4. Free is slot 6, so the farthest candidate bucket is 6 - 3 = 3. Bucket 3 owns D in slot 4 (offset 1), which is before slot 6, so D moves to slot 6, now at offset 3 from its home and still legal. Bucket 3's bitmap changes from 0100 to 0001. Slot 4 is free, at distance 3 from F's home, which is below H, so F goes there and bucket 1 reads 1101. Running the code on these inputs produced exactly this layout: [., A, B, C, F, E, D, .].

A lookup for F now reads bucket 1's bitmap, checks slots 1, 2 and 4, and finds F on the third comparison, without touching slot 3.

How full can it get?

H controls how full the table can get before an insertion fails and forces a resize. To measure it, tables of 2¹⁴ slots were filled with uniformly random 64-bit hashes, without resizing, until the first insertion failed. Ten seeds per H:

These are this article's own measurements with the code above, not figures from the paper, but they show the shape: small neighbourhoods fail early, and H = 32 runs comfortably to about 0.88. A practical policy is to resize at a fixed maximum load (0.8 to 0.9 for H = 32) and treat a hop failure below that load as a signal that the hash function is weak.

Deletion and resizing

Deletion is the easy case, and one of hopscotch's advantages over linear probing. Find the key through the bitmap, empty the slot, and clear the bit. No tombstones are needed, because lookups follow the bitmap rather than scanning until an empty slot, so a hole cannot cut a probe sequence short. Tables that churn do not slowly fill with deleted markers the way linear-probing tables do.

Resizing rehashes every key into a table twice the size, which is O(n) but amortized to O(1) per insertion. Store the full hash beside each key if rehashing is expensive (long string keys), at the cost of memory.

Why it was designed for concurrency

The original paper's goal was a concurrent table. Hopscotch suits concurrency because every operation touches a bounded region: an insertion modifies only the slots and bitmaps along its hop path, all within a short window of the array. The authors' design partitions the table into segments guarded by locks for writers, while readers do not lock. A reader can still race with a hop that moves the key it is looking for, so each segment carries a version counter (the paper calls it a timestamp) that a displacement increments; a reader that sees the counter change during its search retries.

Cuckoo hashing, by contrast, may relocate a chain of keys across unrelated parts of the table during one insert, which makes fine-grained locking much harder. In single-threaded code the benefit is cache behaviour instead: with 8-byte keys and values, a 32-slot neighbourhood spans 512 bytes, but most keys sit within their first few slots, so a typical hit reads one cache line.

Failure modes

• Weak hash functions. If many keys share low bits, the modulo sends them to the same buckets, neighbourhoods saturate, and the table resizes at low load. Use a well-mixed hash and a power-of-two size only with a good finalizer.
• More than H identical hashes. Duplicate hashes, adversarial keys or a constant hash make insertion impossible at any size. Cap resizes, as the code does, or keep an overflow structure. Tessil's C++ hopscotch_map, for example, exposes an overflow_size() count, and its bhopscotch variants keep overflowed elements in a binary search tree.
• Untrusted keys. Anyone who can choose keys can target one bucket. Use a keyed hash such as SipHash for request-controlled keys.
• Lost bitmap updates. A displacement must update the bitmap and move the key together. Under concurrency, do both inside the segment lock and bump the version counter before readers can observe the intermediate state.
• Wrap-around bugs. Neighbourhoods cross the end of the array. Either index modulo n everywhere or allocate H-1 extra slots at the end, never both.

Trade-offs

Hopscotch wins when you need a hard bound on lookup work, high load, frequent deletes or a concurrent design. It loses to a plain linear-probing or SIMD-group table when single-threaded speed on a modern CPU is all that matters, because the bitmap and hop logic add instructions that a tight probe loop does not have.

What to do next

1. Implement the table, then reproduce the six-key example and confirm the layout [., A, B, C, F, E, D, .].
2. Add the invariant check and run it after a randomized workload against a dict.
3. Reproduce the load table for H = 8 and H = 32, then repeat it with a deliberately weak hash (for example keys that are multiples of 64 with a power-of-two table).
4. Benchmark lookups against linear probing at loads of 0.5, 0.8 and 0.9 and plot the probe counts.
5. Before adopting hopscotch in production, compare it with your language's standard map on your real key distribution; adopt it only for a measured win or a concurrency need.
6. Read the hash table article for the wider design space, then the cuckoo hashing article and the cuckoo filter article for the main alternative.