= Tombstone in open addressing
A deleted-slot marker in <open addressing>. Lookup continues past it because a <hash collision> may have displaced a match further along. <Linear probing> can reuse the slot for insertion after checking for an existing equal key. A genuinely empty slot can terminate lookup; this marker cannot.<Open Data Structures: An Introduction by Pat Morin/5.2 LinearHashTable: Linear Probing>[Open Data Structures: An Introduction by Pat Morin; section 5.2, find, add, remove, and correctness paragraph distinguishing del from nil]{ref}
Delete <hash table key> $8$ from the original eight-slot example. Writing `E` into <array index> $1$ makes lookup of $16$ inspect $0,1$ and incorrectly report absence, although its <hash table record> remains at $2$. Writing `D` instead makes lookup pass $1$ and reach $2$, returning $C$ after three <hash table probes>. The deleted slot must remember that the search route once continued through it.
\Image[/linear-probing-deletion-search-paths.png]
{title=Deleting to an empty slot breaks lookup; a <tombstone in open addressing> preserves the search route}
{id=linear-probing-deletion-search-paths}
{description=Original deterministic comparison: the middle and lower rows are alternative deletions from the top row. `E` means never used and stops lookup; `D` means deleted and lets lookup continue. Orange numbers give the <hash table probe> order for <hash table key> $16$.}
A short <algorithm correctness> proof uses this invariant: no never-used slot precedes a stored <hash table key> along its <linear probing> route. Initially the claim is vacuous. Insertion places a new <hash table record> no later than the first `E`, possibly at an earlier `D`, and cannot create an `E` before another stored <hash table record>. Replacing a value leaves all slots occupied as before. Deletion to `D` also creates no `E`. By <mathematical induction> over operations, the invariant persists, so stopping lookup at `E` is sound. Deletion directly to `E` invalidates that argument, as the diagram shows.
To implement the <hash table> map operation `put(k,v)` in one bounded scan, remember the first `D` encountered, but keep checking occupied <hash table keys>. A later <key equality> match means replace that <hash table record>'s value and stop. Only after reaching `E`, or completing $m$ <hash table probes>, is absence established. Then insert at the remembered `D`, if any; otherwise use the stopping `E`. If all $m$ slots are occupied and no match exists, report full or rebuild before trying again. Merely finding `D` is not permission to create a second equal <hash table key>.<Open Data Structures: An Introduction by Pat Morin/5.2 LinearHashTable: Linear Probing>[Open Data Structures: An Introduction by Pat Morin; Section 5.2, add: test for an existing element before reusing del; the book uses a find pass followed by a placement pass]{ref}
Continue from the correctly deleted example, with <hash table keys> $0,16,9$ at <array indices> $0,2,3$ and `D` at $1$. `put(16,Z)` examines $0,1,2$ and updates the value at $2$, leaving $1$ deleted and retaining three live <hash table records>. Inserting immediately at $1$ would instead create two copies of $16$. Now `put(24,W)` examines $0,1,2,3,4$, proves absence at `E`, and places the new <hash table record> at the remembered <array index> $1$. The <hash table load factor> rises from $3/8$ to $4/8$; reusing `D` avoids extending the <linear probing cluster> to $4$.
For a boundary case, fill all eight slots with <hash table keys> $0,1,\ldots,7$ and then delete all eight to `D`. The live <hash table load factor> is zero, but absent lookup of $16$ still needs eight <hash table probes>. `put(16,C)` also checks eight slots before reusing the first `D`, at <array index> $0$. A loop that waits indefinitely for `E` would never finish in this state. Rebuilding from the live <hash table records> into a fresh <array> removes each <tombstone in open addressing> and restores never-used stopping slots.<Open Data Structures: An Introduction by Pat Morin/5.2 LinearHashTable: Linear Probing>[Open Data Structures: An Introduction by Pat Morin; Section 5.2, resize: reinsert live elements and reset the non-nil count to the live count]{ref}
Back to article page
