Deletion in Open Addressing
You'll learn why simply removing an item from an open-addressed hash table can break lookups—and how tombstone markers solve that problem.
The Problem with Direct Deletion
In open addressing (like linear probing, quadratic probing, or double hashing), when a collision occurs, we search for the next available slot. This creates probe chains—sequences of slots checked during insertion and search.
If you simply delete an element by emptying its slot, you create a gap in the probe chain. Future searches that need to skip over that slot will stop at the empty space, incorrectly concluding the item doesn't exist—even if it's further along the chain.
Analogy: Imagine following footprints in snow to find a friend's house. If someone erases a middle footprint, you might think the trail ends and turn back, never reaching the house that's just ahead.
The Tombstone Solution
Instead of leaving an empty slot, mark deleted positions with a special tombstone (or "deleted marker"). This placeholder tells the hash table:
- During search: "Keep probing—don't stop here."
- During insertion: "This slot is available for reuse."
The tombstone preserves the integrity of probe sequences while allowing the slot to be reclaimed.
How It Works
- Search: Treat tombstones like occupied slots—keep probing.
- Insert: Treat tombstones like empty slots—can overwrite them.
- Delete: Replace the target element with a tombstone marker.
This ensures that searches following a probe chain never prematurely stop, while deleted slots remain usable for future insertions.
Key Takeaway:
In open addressing, deletions must use tombstone markers rather than emptying slots directly, preserving probe chain continuity for correct searches while allowing slot reuse.