Deletion in open addressing — tombstone markers: Visual walkthrough

For the parent overview see the topic note. If you have never met these ideas, keep Hash Functions, Open Addressing and Linear Probing open in another tab — but you won't strictly need them; we build from zero.

Step 1 — What a table and a slot even are

WHAT. A hash table is just a fixed row of boxes, numbered $0, 1, 2, \dots, m - 1$ . We call each box a slot. The number of boxes is $m$ — the table size. In this whole page $m = 7$ , so the slots are $0$ through $6$ .

WHY. Everything else — probing, the bug, the fix — is a rule about which box to look in next. So before any rule, we must be able to point at a box and say "slot 4." No maths yet, just a labelled row.

PICTURE. Below: seven boxes, each with its index written under it. All are currently EMPTY (nothing stored). EMPTY is a real state, not just "blank" — remember that word, it becomes the villain.

Step 2 — The hash function picks a starting box

WHAT. A hash function $h (k)$ is a rule that turns a key $k$ into a slot number — a starting box. We use $h (k) = k mod m$

term by term:

$k$ — the key we want to store (just a number here).
$m = 7$ — the table size from Step 1.
$mod$ — the remainder after dividing. $10 mod 7 = 3$ because $10 = 7 \times 1 + 3$ .
$h (k)$ — the answer: which box to start at.

WHY $mod$ and not something else? We need any key, however large, squeezed into a valid box number $0..6$ . The remainder after dividing by $7$ is always in ${0, \dots, 6}$ — exactly the box range. That is the whole reason $mod$ appears: it is the tool that "wraps" big numbers into the row.

PICTURE. Three keys — call them A, B, C — all satisfy $h = 3$ . Watch all three arrows land on the same box 3. That clash is the seed of the whole story.

Step 3 — A collision, and the probe that resolves it

WHAT. Two keys wanting the same box is a collision. We resolve it by probing: if the box is full, try the next box, then the next. With linear probing the probe sequence is $h (k, i) = (h (k) + i) mod m, i = 0, 1, 2, \dots$

term by term:

$h (k)$ — the starting box from Step 2.
$i$ — the probe number: $i = 0$ is the first try, $i = 1$ the next box, and so on.
$+ i$ — step forward $i$ boxes.
$mod m$ — wrap around if we walk off the right end (box $6 \to$ box $0$ ).
$h (k, i)$ — the box we examine on probe number $i$ .

WHY step by $+ 1$ ? We simply need some rule that visits every box eventually and is easy to reproduce later during search. "Move one box right" is the simplest such rule — that is linear probing. (Other rules exist; this page uses this one.)

PICTURE. Insert A, B, C (all start at 3). A takes box 3. B finds 3 full, steps to box 4. C finds 3 then 4 full, steps to box 5. The green arrows trace each probe walk.

Result: [_ _ _ A B C _].

Step 4 — The invariant: why search is allowed to STOP at EMPTY

WHAT. To find a key we replay its probe walk: start at $h (k)$ , step forward, stop when we see the key or an EMPTY box. Stopping at EMPTY is a promise:

WHY is this true? Because insert and search walk the identical path. When we inserted $k$ we stopped at the first EMPTY box and dropped $k$ there. So nothing before $k$ could have been EMPTY at that moment — otherwise $k$ would have gone there instead. Search relies on this: an EMPTY box genuinely means "the chain ended, $k$ isn't here."

PICTURE. The unbroken green corridor from box 3 to C at box 5. There is no gap. That gap-free corridor is the invariant made visible — and the next step destroys it.

Step 5 — The bug: naive deletion punches a hole

WHAT. Delete B "naively" by setting box 4 back to EMPTY: $[_ _ _ A _ C _]$

WHY it looks fine. B really is gone, and EMPTY is the natural "nothing here" state. Seems complete.

WHY it is broken. Now search for C. Replay C's walk: box 3 (A, not C — probe on), box 4 (EMPTY → STOP). The invariant told search "EMPTY = chain ended," so search reports C not found — even though C sits one box further, at box 5. The blank box 4 lies about the chain ending.

PICTURE. The red X marks the hole at box 4; the red "STOP" shows search quitting one box too soon while C sits unreachable behind it.

Step 6 — The tombstone: a box that says "keep going"

WHAT. Give deletion its own marker: set the box to DELETED, a tombstone (drawn with a †). Now every box has three states: EMPTY, OCCUPIED, DELETED.

$[_ _ _ A † C _]$

The rules that make all three consistent:

WHY it works. The invariant only needed "non-EMPTY before the key." A tombstone is non-EMPTY, so the corridor from box 3 to C is repaired: search walks straight past the † and finds C.

PICTURE. Same table as the bug, but box 4 now holds a yellow †. Follow the blue search arrows: 3 (A, on), 4 (†, keep going), 5 (C ✔). Contrast this directly with Step 5's red STOP.

Step 7 — The cost of tombstones: effective load factor

WHAT. Tombstones never block insert, but they always lengthen search — search must walk past every one. Define the effective load factor $α_{eff} = \frac{n _{occupied} + n _{tombstones}}{m}$

term by term:

$n_{occupied}$ — number of live keys.
$n_{tombstones}$ — number of † markers.
$m$ — table size.
$α_{eff}$ — how "full" the table feels to a search, counting graves as fullness.

The expected number of probes for an unsuccessful linear-probing search grows as $\approx \frac{1}{2} (1 + \frac{1}{( 1 - α _{eff} ) ^{2}})$

$(1 - α_{eff})$ — the "empty fraction" the search can still find.
Squaring and inverting it: as the table feels full, $α_{eff} \to 1$ , the denominator $\to 0$ , and probe count explodes.

WHY $α_{eff}$ and not the live count? Because the search cannot tell a † from a live key — it walks past both. So its cost tracks $α_{eff}$ , even if real keys are few.

PICTURE. The curve of probes vs $α_{eff}$ shooting toward the sky near $1$ , with the rehash threshold $0.7$ marked. See Load Factor and Rehashing.

The cure — rehashing. When $α_{eff}$ passes a threshold (say $0.7$ ), rebuild: reinsert only OCCUPIED keys into a fresh array, dropping all tombstones. This resets $α_{eff}$ to the true live load factor.

Step 8 — The degenerate case insert must handle: duplicate keys

WHAT. During insert, a tombstone looks like free space — tempting to drop the new key there instantly. But the key might already exist further down the chain (inserted before that deletion). Stopping at the first † could create a duplicate.

WHY. Consider [_ _ _ A † C _] and we insert C again. Box 3 (A), box 4 (†) — if we stopped here we'd write a second C, while the real C already lives at box 5. Two Cs — corrupt.

The rule: remember the first † you pass, but keep scanning to EMPTY (or the key). Only if the key is absent do you place it at the remembered †.

PICTURE. Insert-of-C walk: mark the † at box 4 as "remembered" (pale outline), keep scanning, hit C at box 5 → do not insert, no duplicate. The dashed arrow shows the scan continuing past the remembered slot.

The one-picture summary

Below, the whole story on one board: the gap-free chain (invariant), the red hole (bug), the yellow tombstone (fix), and the search corridor walking cleanly past the grave.

Recall Feynman: retell the whole walkthrough in plain words

You have a row of numbered lockers. A rule tells you where to start looking (the remainder trick), and if that locker is taken you shuffle to the next one — that's how three friends whose numbers all point to locker 3 end up at 3, 4, 5. To find a friend you retrace that shuffle and stop when you reach them or an empty locker, because an empty locker honestly means "the trail ended." Now if you empty a middle locker to delete someone, you plant a lie: the next searcher hits that empty locker and quits too soon, missing the friend still sitting further down. The fix is a sticky note that says "someone was here — keep walking." Searchers walk past it and find everyone; but inserters must remember the note yet keep walking too, in case the key already lives further along (else they'd make a twin). The catch: sticky notes pile up and make every trail longer, so once the table feels too full — even with few real friends — you clear the whole row and re-place everyone neatly. That clearing is rehashing.

Forecast-then-Verify

Recall Forecast:

$m = 5$ , $h (k) = k mod 5$ . Insert 5, 10, 15 (all hash to 0), delete 10, then search 15 — how many probes? Insert: 5→slot0, 10→slot1, 15→slot2 → [5 10 15 _ _]. Delete 10 → [5 † 15 _ _]. Search 15: slot0 (=5, on), slot1 (=†, keep going), slot2 (=15 ✔). 3 probes. Naive EMPTY would stop at slot1 → falsely "not found."

Connections

Parent topic — the full note.
Open Addressing — the family this lives in.
Linear Probing — the $+ i$ probe rule used throughout.
Hash Functions — the $h (k) = k mod m$ that starts every walk.
Load Factor and Rehashing — why $α_{eff}$ forces the rebuild in Step 7.
Separate Chaining — the alternative where deletion is trivially O(1).