Introduction

Deletion is hard in an open-addressed hash table because empty slots have meaning. A lookup stops when it reaches a slot that has never been occupied, so if deletion turns a used slot back into a normal empty slot, later searches may stop too early and incorrectly conclude that a key is missing.

Why Lookup Depends on Probe Continuity

In open addressing, all keys live inside the table array itself. When a collision occurs, the table follows a probe sequence until it finds a free slot.

With linear probing, for example, keys that collide form a cluster. Lookup works by replaying the same probe sequence used during insertion.

Imagine a table of size 7 and a simple hash of key % 7.

• insert 10, which goes to slot 3
• insert 17, which also hashes to slot 3, so it goes to slot 4
• insert 24, which also hashes to slot 3, so it goes to slot 5

A lookup for 24 starts at slot 3, then probes 4, then 5.

If you delete 17 and make slot 4 look truly empty, the lookup for 24 stops at slot 4 and falsely reports “not found.” That is the core difficulty.

Tombstones Preserve the Probe Chain

The standard solution is lazy deletion: mark the slot as deleted, but do not mark it as never used. This special marker is often called a tombstone.

During lookup:

• a tombstone does not stop the probe
• a never-used slot does stop the probe

During insertion:

• a tombstone can often be reused for a new key

Here is a small Python implementation of linear probing with tombstones.

1EMPTY = object()
2DELETED = object()
3
4class OpenAddressHashTable:
5    def __init__(self, size=8):
6        self.slots = [EMPTY] * size
7
8    def _index(self, key, step):
9        return (hash(key) + step) % len(self.slots)
10
11    def insert(self, key):
12        first_deleted = None
13        for step in range(len(self.slots)):
14            i = self._index(key, step)
15            if self.slots[i] is DELETED and first_deleted is None:
16                first_deleted = i
17            elif self.slots[i] is EMPTY:
18                self.slots[first_deleted if first_deleted is not None else i] = key
19                return
20            elif self.slots[i] == key:
21                return
22        raise RuntimeError("table full")
23
24    def contains(self, key):
25        for step in range(len(self.slots)):
26            i = self._index(key, step)
27            if self.slots[i] is EMPTY:
28                return False
29            if self.slots[i] == key:
30                return True
31        return False
32
33    def delete(self, key):
34        for step in range(len(self.slots)):
35            i = self._index(key, step)
36            if self.slots[i] is EMPTY:
37                return False
38            if self.slots[i] == key:
39                self.slots[i] = DELETED
40                return True
41        return False

This works because lookup distinguishes between “deleted” and “never occupied.”

Why Tombstones Are Not Free

Tombstones preserve correctness, but they degrade performance over time. A table with many deletions accumulates dead slots that still need to be probed during lookup.

That means:

• successful lookups may scan more slots
• failed lookups may scan more slots
• insertions may need extra probing before finding a reusable position

Eventually the implementation may need to rehash the table into a fresh array to remove tombstones and restore short probe sequences.

Backward-Shift Deletion Exists, but Only Sometimes

For linear probing, another strategy is backward-shift deletion. After removing an entry, you shift later entries backward when their probe sequence would still allow them to remain reachable.

That can avoid tombstone buildup, but it is more complex and depends on the probing scheme. What works for linear probing does not translate cleanly to quadratic probing or double hashing.

That is one reason tombstones are such a common default. They are simple and general.

Deletion Is Easy in Chaining, Hard in Open Addressing

This difference becomes clearer when you compare open addressing with chaining.

In chaining, each bucket stores a list or another container. Deleting one entry from that list does not break the search path for other keys in the bucket.

In open addressing, the position of each key is tied to the search path itself. Removing one entry changes the shape of that path unless you preserve it carefully.

So the difficulty is structural, not incidental.

The Real Invariant

The hidden invariant in open addressing is this: every key must remain discoverable by its probe sequence from its original hash position. Deletion is hard because naïvely clearing a slot violates that invariant.

Once you see the table that way, the need for tombstones or careful shifting becomes obvious.

Common Pitfalls

The most common mistake is implementing delete by setting the slot back to empty. That breaks future searches.

Another mistake is reusing tombstones without tracking whether a key might appear later in the same probe chain. Insert logic must keep probing long enough to avoid duplicates.

Developers also forget that too many tombstones harm performance even when correctness is preserved. Rehashing is part of the design, not an optional cleanup.

Finally, do not assume deletion logic for linear probing automatically works for double hashing or quadratic probing.

Summary

• Deletion is difficult in open addressing because empty slots terminate lookup.
• A naïve delete can break the probe chain for keys inserted later.
• Tombstones preserve correctness by marking “deleted” separately from “never used.”
• Tombstones slow the table down over time, so rehashing is often necessary.
• More advanced deletion strategies exist, but they depend heavily on the probing method.