Exercises — Deletion in open addressing — tombstone markers

• Slot 0: _ → EMPTY
• Slot 1: _ → EMPTY
• Slot 2: A → OCCUPIED
• Slot 3: † → DELETED (tombstone)
• Slot 4: C → OCCUPIED
• Slot 5: _ → EMPTY
• Slot 6: _ → EMPTY

Only EMPTY stops an unsuccessful search. OCCUPIED (wrong key) and DELETED both mean keep probing. Search also stops — successfully — when it lands on the key itself.

All three hash to $10\mathrm{mod}7=3$, $17\mathrm{mod}7=3$, $24\mathrm{mod}7=3$ — same home slot 3.

• Insert 10: slot 3 free → [_ _ _ 10 _ _ _]
• Insert 17: slot 3 taken → probe 4 (free) → [_ _ _ 10 17 _ _]
• Insert 24: slot 3, 4 taken → probe 5 (free) → [_ _ _ 10 17 24 _]
• Delete 17: locate at slot 4, set DELETED → [_ _ _ 10 † 24 _]

Figure s02 animates this exact build as four stacked snapshots — watch the chain grow at slots 3→4→5, then slot 4 flip to a magenta tombstone in the last row.

$h(24)=3$. Probe slot 3 (=10, not it) → slot 4 (=†, keep going) → slot 5 (=24 ✔). 3 probes. If slot 4 had been blanked to EMPTY, search would stop at slot 4 (2 probes) and wrongly report 24 missing.

Figure s03 contrasts the two searches side by side: the tombstone chain (top) walks through to 24; the wrongly-EMPTY chain (bottom) dead-ends at slot 4.

$h(31)=3$. Probe slot 3 (10, no) → 4 (†, keep going) → 5 (24, no) → 6 (_ EMPTY → STOP). 4 probes, then correctly reports absent. The tombstone forced one extra probe compared with a clean table — this is the tombstone's cost in action.

$h(45)=3$. Insert scans the probe chain, remembering the first tombstone but not stopping there:

• slot 3: OCCUPIED (10) → not 45, remember nothing yet, continue
• slot 4: † → remember "first tombstone = slot 4", continue (must check for a duplicate 45 further on)
• slot 5: OCCUPIED (24) → not 45, continue
• slot 6: _ EMPTY → chain ends, no duplicate 45 exists.

Now place 45 at the remembered tombstone, slot 4: [_ _ _ 10 45 24 _]. Insert reused the grave and shortened future chains — the tombstone paid off.

Wrong (stop-early) path: insert sees † at slot 4 and drops 24 there → [_ _ _ 10 24 24 _]. Now two copies of 24 exist. A later search finds the slot-4 copy; delete it, and the slot-5 copy is orphaned — corruption. Correct path: scan past the tombstone: slot 4 (†, remember) → slot 5 (=24, key already present!) → stop, do not insert a duplicate (update in place if needed). No duplicate created. This is exactly why insert must scan to EMPTY-or-key even after finding a reusable tombstone.

${\alpha }_{\text{eff}}=\frac{n_{\text{occ}}+n_{\text{tomb}}}{m}=\frac{3+4}{10}=0.7$. ${\alpha }_{\text{live}}=\frac{3}{10}=0.3$.

With tombstones (${\alpha }_{\text{eff}}=0.7$): $\frac{1}{2}\left(1+\frac{1}{(1-0.7{)}^2}\right)=\frac{1}{2}\left(1+\frac{1}{0.09}\right)=\frac{1}{2}(1+11.111\dots )\approx 6.06\text{ probes.}$ After purging tombstones ($\alpha =0.3$): $\frac{1}{2}\left(1+\frac{1}{(1-0.3{)}^2}\right)=\frac{1}{2}\left(1+\frac{1}{0.49}\right)=\frac{1}{2}(1+2.041)\approx 1.52\text{ probes.}$ The tombstones nearly quadruple the search cost while only 3 real keys live in a size-10 table. This is the concrete reason to rehash.

$h(9)=4$. Probe starts at the last slot:

• $i=0$: index $(4+0)\mathrm{mod}5=4$ → OCCUPIED (24), continue.
• $i=1$: index $(4+1)\mathrm{mod}5=0$ → the \bmod m wraps around to slot 0, which is EMPTY.

Place 9 at slot 0: [9 _ _ 20 24]. The mod m in $h(k,i)=(h(k)+i)\mathrm{mod}m$ is exactly what makes probing circular — running off index 4 loops back to index 0, so the array behaves like a ring, never a dead-end. Every search and insert in the earlier exercises silently relied on this; here we saw it fire.

(a) Before the delete. Count occupied plus tombstones over $m$: ${\alpha }_{\text{eff}}=\frac{n_{\text{occ}}+n_{\text{tomb}}}{m}=\frac{4+2}{8}=\frac{6}{8}=\mathrm{0.75.}$ Already $0.75>0.7$ — the table was over threshold before we even touched it.

(b) After the delete. A delete converts one OCCUPIED slot into a tombstone: $n_{\text{occ}}$ drops from 4 to 3, $n_{\text{tomb}}$ rises from 2 to 3. The sum is unchanged: ${\alpha }_{\text{eff}}=\frac{3+3}{8}=\frac{6}{8}=\mathrm{0.75.}$ Deletion never lowers ${\alpha }_{\text{eff}}$ — it just swaps one counted state for another.

(c) Verdict. $0.75>0.7$, so the policy triggers a rehash. Rehashing reinserts only the 3 live keys into a fresh array (the 3 tombstones are dropped). Keeping $m=8$, the reset value is ${\alpha }_{\text{eff}}=\frac{3+0}{8}=\frac{3}{8}=\mathrm{0.375.}$ Rehash is the only operation that actually shrinks ${\alpha }_{\text{eff}}$, because it is the only one that removes tombstones from the count.

All of 5,10,15,20 hash to $0$ (since each is a multiple of 5). Chain builds at slots 0,1,2,...

1. insert 5 → slot 0: [5 _ _ _ _]
2. insert 10 → slot 0 taken → slot 1: [5 10 _ _ _]
3. insert 15 → 0,1 taken → slot 2: [5 10 15 _ _]
4. delete 10 → slot 1 becomes †: [5 † 15 _ _]
5. insert 20 → probe slot 0 (5, no), slot 1 (†, remember), slot 2 (15, no), slot 3 (_ EMPTY, chain ends, no duplicate 20) → place at remembered tombstone slot 1: [5 20 15 _ _]
6. search 15 → slot 0 (5, no) → slot 1 (20, no) → slot 2 (15 ✔): 3 probes.

Insert step 5 reused the grave, so after it there are no tombstones left and the chain stays tight.

Invariant. If key $k$ is present at position $h(k,j)$, then for every $i<j$, the slot $h(k,i)$ is not EMPTY (it is OCCUPIED or DELETED). Why deletion-to-tombstone preserves it. Consider deleting some key $x$ that sat at a slot $s$ on $k$'s probe chain, i.e. $s=h(k,i)$ for some $i<j$. Before deletion, slot $s$ was OCCUPIED, so the invariant held.

• If we set $s$ to EMPTY, then $h(k,i)$ becomes EMPTY with $i<j$ — the invariant is violated, and a search for $k$ stops at slot $s$, failing to reach position $j$.
• If we set $s$ to DELETED, then $h(k,i)$ is still "not EMPTY" — the invariant still holds. Search treats DELETED like OCCUPIED, walks past $s$, and reaches $k$ at position $j$. ∎

The tombstone is precisely the minimal change that keeps "not EMPTY" true for every intermediate slot without pretending a live key is present.

Separate chaining: each bucket is a linked list; deleting a key just unlinks a node — O(1), and it genuinely removes the entry with no side effect on any other key's lookup (each key's chain is independent of others). There is no shared probe path to corrupt, so no tombstone concept exists and ${\alpha }_{\text{eff}}$ never gets inflated by deletions. Open addressing: all keys share one array and probe paths overlap; a blanked slot corrupts every chain threading through it. Tombstones repair this but inflate ${\alpha }_{\text{eff}}=\frac{n_{\text{occ}}+n_{\text{tomb}}}{m}$, so search slows and periodic rehashing is mandatory. When open addressing still wins: with cache locality and low load factor and rare deletions. Contiguous array probing hits far fewer cache lines than pointer-chasing a linked list. If the workload is read-heavy with occasional deletes (tombstones rare, rehash rare), open addressing's fast searches and compact memory outperform chaining's pointer overhead — the O(1) delete of chaining doesn't matter if you delete seldom.

What a rehash does, entry by entry. It scans all $m$ slots of the old array. For each slot it looks at the state:

• EMPTY → skip (nothing to move).
• DELETED (†) → skip and drop — tombstones are not carried over.
• OCCUPIED → reinsert the live key into the fresh array.

So of the up-to-$0.7m$ counted entries, only the live (OCCUPIED) ones are reinserted; every tombstone evaporates. Because the trigger fired at ${\alpha }_{\text{eff}}=0.7$, the number of live keys is at most $0.7m$ (fewer if some of the count was tombstones).

Why the new ${\alpha }_{\text{eff}}\le 0.35$. Those $\le 0.7m$ live keys go into an array of the doubled size $2m$, and no tombstones exist right after a rebuild, so ${\alpha }_{\text{eff}}^{\text{new}}=\frac{n_{\text{occ}}+0}{2m}\le \frac{0.7m}{2m}=\mathrm{0.35.}$

The amortised argument. A rehash costs O(m): scan $m$ slots + reinsert $\le 0.7m$ keys. To climb from the post-rebuild value ($\le 0.35$) back up to the trigger ($0.7$) at the doubled size $2m$, you must perform at least $(0.7-0.35)\cdot 2m=0.35\cdot 2m=\Theta (m)$ counted operations (each insert or delete bumps $n_{\text{occ}}+n_{\text{tomb}}$ by one). Spreading the O(m) rebuild over those $\Theta (m)$ operations gives $\frac{O(m)}{\Theta (m)}=O(1)\text{ amortised per operation.}$ Each individual insert/search/delete is O(1) expected at bounded load factor, so the amortised per-operation cost is O(1) — the same "charge the rebuild to the operations that filled the table" accounting used for dynamic array doubling. ∎