Hopscotch hashing: keep each shipment near its home bucket

Last updated: 5 Oct 20269 min read

tutorial

Hopscotch hashing is an open-addressed set with a fixed neighborhood width. Every resident key stays within H circular slots after its hash home. Lookup can inspect just those H slots; insertion first locates an empty slot and, when it lies too far away, repeatedly moves a nearby occupant into that hole if the occupant still remains inside its own home neighborhood. The hole then moves backward toward the incoming key's home. If no legal relocation exists, insertion reports failure even if other table slots remain empty. This teaching set uses direct neighborhood scans rather than a bitmap of hop information, and it has no automatic resize. Deletion clears the matching slot because lookup scans the whole allowed neighborhood; no linear-probe tombstone chain is needed. Integer IDs are its declared key domain.

Operational case

At capacity 31 and neighborhood width five, shipment IDs 47, 78, 109, 140, and 171 fit in the displayed trace. ID 202 is rejected because no legal series of local moves places it within its own five-slot home window. That rejection does not discard the earlier shipments. Removing 109 makes its lookup false and leaves four residents. The failed insertion may have relocated existing keys, so callers should rely on set membership and the neighborhood invariant rather than byte-for-byte slot stability. The hash multiplier here is deterministic for reproducibility, not a defense against adversarial keys.

Working Python program

class ShipmentNeighborhoodSet:
    def __init__(self, capacity=31, neighborhood=5):
        if capacity < 2 or not 1 <= neighborhood <= capacity:
            raise ValueError("invalid capacity or neighborhood")
        self.capacity = capacity
        self.neighborhood = neighborhood
        self.slots = [None] * capacity
        self.count = 0

    def _home(self, shipment_id):
        return (shipment_id * 2654435761) % self.capacity

    def _distance(self, start, stop):
        return (stop - start) % self.capacity

    def contains(self, shipment_id):
        home = self._home(shipment_id)
        return any(self.slots[(home + step) % self.capacity] == shipment_id
                   for step in range(self.neighborhood))

    def add(self, shipment_id):
        if not isinstance(shipment_id, int):
            raise TypeError("shipment ID must be an integer")
        if self.contains(shipment_id):
            return True
        home = self._home(shipment_id)
        free = next(((home + step) % self.capacity for step in range(self.capacity)
                     if self.slots[(home + step) % self.capacity] is None), None)
        if free is None:
            return False
        while self._distance(home, free) >= self.neighborhood:
            moved = False
            for backward in range(self.neighborhood - 1, 0, -1):
                candidate = (free - backward) % self.capacity
                occupant = self.slots[candidate]
                if occupant is None:
                    continue
                if self._distance(self._home(occupant), free) < self.neighborhood:
                    self.slots[free] = occupant
                    self.slots[candidate] = None
                    free = candidate
                    moved = True
                    break
            if not moved:
                return False
        self.slots[free] = shipment_id
        self.count += 1
        return True

    def discard(self, shipment_id):
        home = self._home(shipment_id)
        for step in range(self.neighborhood):
            slot = (home + step) % self.capacity
            if self.slots[slot] == shipment_id:
                self.slots[slot] = None
                self.count -= 1
                return True
        return False


if __name__ == "__main__":
    registry = ShipmentNeighborhoodSet(capacity=31, neighborhood=5)
    for shipment_id in [47, 78, 109, 140, 171, 202]:
        print(shipment_id, registry.add(shipment_id))
    print(registry.contains(109), registry.discard(109), registry.contains(109))
    print(registry.count)

Output

47 True
78 True
109 True
140 True
171 True
202 False
True True False
4

Time, space, and tradeoff

Lookup and deletion inspect at most H slots, giving O(H) time and O(1) auxiliary space. Finding a hole can scan C slots in a capacity-C table. Each relocation checks at most H minus one candidates, and up to C relocations may occur, so this direct implementation has O(CH) worst-case insertion time and O(C) storage. A failed insertion can still pay that work. At high occupancy, legal placement can fail before the array is full; resizing and rehashing would be a separate operation. Robin Hood hashing instead controls probe-distance balance, while this structure enforces a hard locality window.

Common Mistakes

Do not move a resident outside its own home neighborhood.
Do not promise insertion succeeds merely because a distant empty slot exists.
Do not assume slot positions remain stable after a failed placement attempt.
Do not call this direct-scan model a concurrent hopscotch table.

Connected lessons

Compare the operation boundary with Double-array tries: static incident-code transitions with BASE and CHECK, Invertible Bloom tables: peel differences between replica ID sets, De Bruijn graphs: compact non-branching k-mer routes into unitigs, then complete the audit project and decision quiz.

data structures

range-query-structures