Noesis
3.3.5Hashing

Deletion in open addressing — tombstone markers

1,880 words9 min readdifficulty · medium
🇮🇳 Yeh note Hinglish mein padho →

The whole insert/search invariant is:

Now suppose we delete by setting a slot to EMPTY:

HOW the tombstone fixes it

Rules that make everything consistent:

Figure — Deletion in open addressing — tombstone markers

The cost: tombstone accumulation

The cure: rehashing. When tombstones grow too numerous (e.g. αeff\alpha_{\text{eff}} exceeds a threshold like 0.70.7), rebuild the table: reinsert only OCCUPIED entries into a fresh array, dropping all tombstones. This resets αeff\alpha_{\text{eff}} to the true live load factor.

Forecast-then-Verify

Recall Forecast: m=5, h(k)=k mod 5, linear probing. Insert 5,10,15 (all hash to 0). Then delete 10. Search for 15 — how many probes, and what does each slot read?

Insert: 5→slot0, 10→slot1, 15→slot2. Table [5 10 15 _ _]. Delete 10 → tombstone: [5 † 15 _ _]. Search 15: probe slot0 (=5, no), slot1 (=†, keep going), slot2 (=15 ✔). 3 probes. Without tombstones, slot1 EMPTY would have stopped the search at 2 probes and falsely reported "not found."

Common mistakes

80/20 — the must-keep ideas

  1. EMPTY means "stop searching"; deleting to EMPTY breaks chains.
  2. Tombstone (DELETED) = "key gone, but keep probing."
  3. Search treats DELETED like occupied; insert may reuse it (but scan on for duplicates).
  4. Tombstones bloat αeff\alpha_{\text{eff}} → rehash when too many.

Flashcards

Why can't you delete in open addressing by setting the slot to EMPTY?
EMPTY means "probe sequence ends," so blanking a middle slot makes later searches in that chain stop early and report keys as missing.
What is a tombstone marker?
A special DELETED slot state meaning "a key was removed here, but keep probing" — it preserves the search chain.
How does SEARCH treat a tombstone?
Like an occupied slot — it keeps probing; it only stops on EMPTY or on finding the key.
How does INSERT treat a tombstone?
As reusable free space: remember the first tombstone, but keep scanning to EMPTY to ensure no duplicate exists, then place the key at the remembered tombstone.
What are the three slot states in open addressing with deletion?
EMPTY, OCCUPIED, DELETED (tombstone).
What is the effective load factor and why does it matter?
αeff=(noccupied+ntombstones)/m\alpha_{eff} = (n_{occupied}+n_{tombstones})/m; search cost depends on it, so tombstones slow lookups even with few live keys.
How do you get rid of accumulated tombstones?
Rehash/rebuild: reinsert only OCCUPIED entries into a fresh table, dropping all tombstones; resets αeff\alpha_{eff}.
In insert, why keep scanning past the first tombstone instead of placing the key immediately?
The key may already exist further along the probe chain; stopping early risks inserting a duplicate.
Recall Feynman: explain to a 12-year-old

Imagine a row of lockers and a rule for finding your stuff: "start at locker 3; if it's not yours, try the next, and the next — until you find yours OR you hit an empty locker, which means stop, your stuff isn't here." Now if someone empties a locker in the middle of your trail, you'll hit that empty locker and quit too soon, missing your stuff in the next locker. So instead of leaving it empty, we put a little "used to be here" sticky note (a tombstone). When you see the sticky note you think "keep going!" and you find your stuff. After lots of stickies pile up, the trails get long, so once in a while we clear the whole row and re-place everything neatly.

Connections

  • Open Addressing — the family this deletion problem belongs to.
  • Linear Probing — probe sequence used in the examples.
  • Load Factor and Rehashing — why αeff\alpha_{\text{eff}} forces rebuilds.
  • Separate Chaining — alternative where deletion is trivially O(1) (just unlink).
  • Hash Functions — the h(k)h(k) that starts every probe.

Concept Map

uses

stops at

broken by

punches

causes

fixed by

adds

search

insert

preserves

accumulates

measured by

Open addressing

Probe sequence

Search-stops-at-EMPTY invariant

Naive delete sets EMPTY

Hole in probe chain

Search gives up too early

Tombstone DELETED marker

Three slot states

Keep probing past DELETED

Treat as free slot

Long probe sequences

Effective load factor

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Open addressing me saare keys ek hi array ke andar rehte hain (koi linked list nahi). Kisi key ko dhoondhne ke liye hum probe karte hain — slot h(k)h(k) se shuru karke agle-agle slots check karte hain, jab tak key mil na jaye ya ek EMPTY slot na aa jaye. EMPTY ka matlab hota hai "bas, ruk jao, key yahan nahi hai." Yahi rule problem create karta hai jab hum delete karte hain.

Maan lo aapne ek key ko delete karke uska slot bilkul EMPTY kar diya. Ab us slot ke "aage" jo dusri key padi thi (jo collision ki wajah se aage chali gayi thi), uski search beech me EMPTY dekh kar ruk jayegi aur galat keh degi "key nahi mili." Isiliye hum slot ko EMPTY nahi, balki ek special tombstone (DELETED marker) laga dete hain. Tombstone bolta hai: "yahan koi tha, ab nahi hai, par tum probing continue karo." Search tombstone ko occupied jaisa treat karke aage badh jaati hai aur sahi key dhoond leti hai.

Insert ke time tombstone ko free slot ki tarah use kar sakte ho, lekin dhyaan rakhna — pehle tombstone pe rukna mat, aage tak scan karna padta hai taaki duplicate na ban jaye (kyunki key shayad chain me aage already maujood ho). Aur ek cost hai: tombstones dheere-dheere jam jaate hain, jisse αeff\alpha_{eff} badhta hai aur search slow ho jaati hai chahe asli keys kam ho. Iska ilaaj: jab tombstones zyada ho jaayein to rehash karo — sirf OCCUPIED entries ko naye table me daalo, tombstones ko phenk do. Bas itna yaad rakho: "EMPTY = stop, tombstone = keep going."

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,818 wordsD2Visual walkthroughThe derivation in pictures · 2,097 wordsD3Worked examplesEvery scenario covered · 2,640 wordsD4ExercisesGraded, full solutions · 3,354 wordsD5Question bankConcept traps, quick reveals · 2,129 words

Test yourself — Hashing

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Open addressing — linear probing, quadratic probing, double hashingCoding · 3.3.4Load factor — when to resize, rehashing costCoding · 3.3.6