How must insert and lookup treat a tombstone slot differently in an open-addressed hash table?

## Three states, two loops An open-addressed table with deletion support gives every slot one of three states: - **EMPTY** — never used. - **OCCUPIED** — holds a live key/value pair. - **DELETED** (the *tombstone*) — held an entry once; the entry is gone but the probe path through this slot must stay intact. The subtlety is that lookup and insert must interpret DELETED differently, and getting either one wrong produces a distinct bug. ## Lookup: a tombstone is a pass-through For a search, DELETED behaves exactly like an occupied slot holding some other key: not a match, keep probing. Only EMPTY ends the walk. This is the whole reason tombstones exist — they preserve the invariant that every slot from a stored key's home slot up to its position is non-EMPTY, so the walk always reaches the key. A consequence worth stating out loud: **misses pay more than hits.** A successful lookup stops the moment it finds its key, often after one or two probes. An unsuccessful lookup has no early exit — it must run all the way to the first EMPTY slot. In a table full of tombstones, hit latency barely moves while miss latency climbs steeply. ## Insert: reuse, but do not stop Insertion is allowed to recycle a tombstone; that is a genuine optimisation, since it turns dead space back into live space without any rebuild. But the reuse must not short-circuit the search, and this is where implementations go wrong. The correct shape is: 1. Walk the probe sequence from the home slot. 2. On the **first** DELETED slot seen, remember its index — and continue. 3. On an OCCUPIED slot whose key matches, update in place and return. (The existing entry wins; a duplicate must never be created.) 4. On EMPTY, the key is definitely not present. Write the entry into the remembered tombstone if there was one; otherwise write it into the EMPTY slot. Skipping step 2's "and continue" produces **duplicate keys**. Suppose key K sits at slot 12, and slot 9 on the same path is a tombstone. An insert for K that stops at slot 9 stores a second copy. From then on, lookups find the copy at 9 and the entry at 12 is a shadow: a delete removes one and the other reappears, an update mutates one while readers see the other. It is a data-integrity bug, not a performance bug, and it is invisible until a key happens to be re-inserted over a path containing a tombstone. One detail people miss in step 4: if the search ran to EMPTY *without* passing a tombstone, the entry goes into that EMPTY slot as usual. Reuse is opportunistic, never mandatory. ## Accounting: which counter drives what A table with deletions needs two counts, and confusing them is the second common defect: | Counter | Changes on | Used for | |---|---|---| | live entries | +1 insert of a new key, −1 delete | reported size, sizing a rebuild | | non-empty slots (live + tombstones) | +1 when an EMPTY slot is consumed; never falls without a rebuild | the load-factor test that decides when to rebuild | Probe length depends on how much of the array is **not EMPTY**, not on how much of it is live — a probe step over a tombstone costs the same slot read and state check as a step over an occupied slot. So the load-factor test must use the non-empty count. A table at 30% live occupancy can be at 90% non-empty occupancy and behave like a nearly full table. Note the asymmetry that makes this an invariant rather than a heuristic: deleting turns OCCUPIED into DELETED (non-empty count unchanged), and reusing turns DELETED back into OCCUPIED (non-empty count unchanged again). The only operation that consumes an EMPTY slot is an insert that found no tombstone on its path. **Nothing except a rebuild ever gives an EMPTY slot back.** Reuse helps — it can drive the tombstone count down — but it only recycles tombstones that happen to lie on some future key's probe path, so it cannot be relied on to bound the dead space. ## What interviewers listen for The answer they are grading is whether you volunteer the "remember it, keep probing" rule without being prompted, and whether you can name what breaks if you don't. A candidate who says "a tombstone is a free slot, so insert takes it" has described a duplicate-key generator. A candidate who adds that the load-factor test has to count tombstones has connected the correctness rule to the performance consequence, which is the middle-tier bar for this topic.