Open-addressed hash tables: tombstones and rebuilds

Last updated: 7 Oct 20269 min read

tutorial

Linear probing stores a key-value pair in an array slot found by walking forward from its hash position. Lookup stops at a truly empty slot; a deleted slot cannot be made empty if later colliding keys might lie beyond it. A tombstone marks that slot as available for later insertion while telling lookup to keep probing. This example tracks live entries and tombstones separately and rebuilds the table when occupied or formerly occupied slots approach its load threshold. A rebuild reinserts live entries and removes tombstones. It accepts nonnegative integer bay IDs; this simple modulo hash is intentionally transparent and vulnerable to clustered or adversarial IDs.

Operational case

With eleven initial slots, bay IDs 47, 58, and 69 all start at the same remainder and form a probe run. Deleting 47 must not hide 58 or 69. The program prints successful lookups for both survivors, then inserts bay 80 and checks that it can be found while 47 remains absent. A tombstone can be reused, but a search for an existing key must continue past earlier tombstones before insertion decides where to write. If enough tombstones collect, even unsuccessful lookups walk long runs until the table is rebuilt.

Working Python program

TOMBSTONE = object()


class BayDirectory:
    def __init__(self, capacity=11):
        self.slots = [None] * capacity
        self.live = 0
        self.deleted = 0

    def locate(self, bay_id):
        first_deleted = None
        for offset in range(len(self.slots)):
            index = (bay_id + offset) % len(self.slots)
            entry = self.slots[index]
            if entry is None:
                return first_deleted if first_deleted is not None else index, False
            if entry is TOMBSTONE:
                if first_deleted is None:
                    first_deleted = index
            elif entry[0] == bay_id:
                return index, True
        return first_deleted, False

    def rebuild(self, capacity):
        old_entries = [entry for entry in self.slots if entry is not None and entry is not TOMBSTONE]
        self.slots = [None] * capacity
        self.live = 0
        self.deleted = 0
        for bay_id, owner in old_entries:
            self.put(bay_id, owner)

    def put(self, bay_id, owner):
        if not isinstance(bay_id, int) or bay_id < 0:
            raise ValueError("bay ID must be a nonnegative integer")
        if 10 * (self.live + self.deleted + 1) >= 7 * len(self.slots):
            self.rebuild(2 * len(self.slots) + 1)
        index, found = self.locate(bay_id)
        if found:
            self.slots[index] = bay_id, owner
            return
        if index is None:
            self.rebuild(2 * len(self.slots) + 1)
            index, _ = self.locate(bay_id)
        if self.slots[index] is TOMBSTONE:
            self.deleted -= 1
        self.slots[index] = bay_id, owner
        self.live += 1

    def lookup(self, bay_id):
        index, found = self.locate(bay_id)
        return (True, self.slots[index][1]) if found else (False, None)

    def remove(self, bay_id):
        index, found = self.locate(bay_id)
        if not found:
            return False
        self.slots[index] = TOMBSTONE
        self.live -= 1
        self.deleted += 1
        if self.deleted > self.live and self.deleted > 2:
            self.rebuild(len(self.slots))
        return True


directory = BayDirectory()
for bay_id, owner in ((47, "north"), (58, "east"), (69, "west")):
    directory.put(bay_id, owner)
print(directory.remove(47), directory.lookup(58), directory.lookup(69))
directory.put(80, "south")
print(directory.lookup(80), directory.lookup(47))

Output

True (True, 'east') (True, 'west')
(True, 'south') (False, None)

Time, space, and tradeoff

Lookup, insertion, and deletion are expected O(1) only under a suitable key distribution and controlled effective load; colliding keys make a single operation O(n) in the table size. A rebuild is O(n) and can pause a writer, though geometrically growing capacity gives amortized expected constant insertion work under typical distributions. The array uses O(n) slots relative to stored entries at the chosen load policy. This implementation treats a missing result as a found boolean plus value, so a stored None value is distinguishable from absence. It is single-threaded and does not use a cryptographic or universal hash function.

Common Mistakes

Do not replace a deleted slot with a truly empty slot inside a collision chain.
Do not insert into the first tombstone before checking for an existing copy of the key later in the run.
Do not measure load using only live entries when tombstones are numerous.
Do not promise O(1) worst-case lookup for colliding integer IDs.

Connected lessons

Apply this operation in the warehouse release project, then check the deletion and dependency quiz.

Robin Hood hashing: probe distance and backward-shift deletion adds a related operation contract.

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

Extendible hashing: split buckets through a shared directory adds a keyed lookup comparison.

data structures

range-query-structures