Robin Hood hashing: probe distance and backward-shift deletion

Last updated: 4 Oct 20269 min read

tutorial

Robin Hood hashing is an open-addressed table that compares each key's distance from its home slot during insertion. When an incoming key has traveled farther than the current occupant, they swap, and the displaced occupant continues probing. Lookup can stop at an empty slot or when the occupant's home distance is smaller than the searcher's current distance; beyond that point the searched key cannot appear while the invariant holds. Deletion shifts later keys backward until it reaches an empty slot or a key already at home. This preserves the lookup stopping rule without a tombstone. The example is a fixed-capacity set of integer asset IDs, not a concurrent hash map.

Operational case

Use seven slots and insert 19, 26, 33, 47, and 54. All five IDs share a home slot modulo seven, creating a visible probe cluster. Asset 47 is present. Removing 26 shifts later cluster members backward; 33 remains findable, and the sorted live IDs are 19, 33, 47, 54. A duplicate insert returns false. Once all slots are occupied, a new distinct ID raises rather than looping forever. Hash quality matters: an attacker who forces collisions can turn every operation into a long scan, regardless of the table's average-case appeal.

Working Python program

"""Fixed-capacity Robin Hood set with backward-shift deletion."""


class AssetSlotSet:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.slots: list[int | None] = [None] * capacity
        self.size = 0

    def _home(self, asset_id: int) -> int:
        return hash(asset_id) % self.capacity

    def _distance(self, asset_id: int, position: int) -> int:
        return (position - self._home(asset_id)) % self.capacity

    def _locate(self, asset_id: int) -> int | None:
        position = self._home(asset_id)
        distance = 0
        while distance < self.capacity:
            occupant = self.slots[position]
            if occupant is None or self._distance(occupant, position) < distance:
                return None
            if occupant == asset_id:
                return position
            position = (position + 1) % self.capacity
            distance += 1
        return None

    def contains(self, asset_id: int) -> bool:
        return self._locate(asset_id) is not None

    def insert(self, asset_id: int) -> bool:
        if self.contains(asset_id):
            return False
        if self.size == self.capacity:
            raise OverflowError("asset slots are full")
        position = self._home(asset_id)
        distance = 0
        incoming = asset_id
        while True:
            occupant = self.slots[position]
            if occupant is None:
                self.slots[position] = incoming
                self.size += 1
                return True
            occupant_distance = self._distance(occupant, position)
            if occupant_distance < distance:
                self.slots[position], incoming = incoming, occupant
                distance = occupant_distance
            position = (position + 1) % self.capacity
            distance += 1

    def remove(self, asset_id: int) -> bool:
        position = self._locate(asset_id)
        if position is None:
            return False
        next_position = (position + 1) % self.capacity
        while self.slots[next_position] is not None and self._distance(self.slots[next_position], next_position) > 0:
            self.slots[position] = self.slots[next_position]
            position = next_position
            next_position = (next_position + 1) % self.capacity
        self.slots[position] = None
        self.size -= 1
        return True


assets = AssetSlotSet(7)
for asset_id in (19, 26, 33, 47, 54):
    assets.insert(asset_id)
print(assets.contains(47))
print(assets.remove(26))
print(assets.contains(33))
print(sorted(asset_id for asset_id in assets.slots if asset_id is not None))

Output

True
True
True
[19, 33, 47, 54]

Time, space, and tradeoff

With fixed capacity C, a lookup, insertion, or deletion probes O(C) slots in the worst case. Backward-shift deletion may move O(C) occupants. Under a suitable hash and controlled load, expected probes are short, but this implementation makes no formal bound for adversarial IDs. Storage is O(C) slots and O(1) working space. The public set does not resize, so callers must choose capacity and handle overflow. Iterators over raw slots are unstable across insertions and deletions because keys move. Compared with tombstones, backward shifting avoids stale markers but pays immediate movement cost at deletion time.

Common Mistakes

Do not stop a lookup merely because its first home slot contains another key.
Do not leave a deletion hole before displaced keys that depend on that probe path.
Do not move a key backward past its home slot.
Do not claim worst-case constant time under collisions or a full table.

Connected lessons

Apply the invariant in the warehouse indexes project, then check the operations quiz.

Cuckoo hashing: relocate keys and recover from cycles adds a related operation contract.

Hopscotch hashing: keep each shipment near its home bucket examines a related structure with a different operation boundary.

data structures

range-query-structures