skip to content

In an open-addressed hash table, why does deleting a key by just emptying its slot break later lookups?

level: juniorimportance: must knowfreq 42%

answer

  1. Ask what makes a search stop
  2. The deleted key was not alone
  3. Colliding keys were pushed further along
  4. An empty slot terminates the probe walk
  5. Mark the slot, do not clear it

basics

~20 s

Emptying the slot cuts a probe path. A lookup walks forward from the home slot and stops at the first empty slot, so a key that collided and landed past the hole is now reported missing even though it is still stored.

solid answer

~50 s

In open addressing every entry lives in the table itself, so a key whose home slot is taken is stored at the next slot its probe sequence reaches. A lookup replays that sequence and stops at the first genuinely empty slot, because empty means "nothing was ever placed past here on this path". If deletion writes EMPTY back into a slot, it punches a hole in the middle of a live probe path: keys stored beyond the hole are still in the table, but the search for them now terminates early and returns not-found. Picture a fraud-check table where a flagged card number collided and was stored one slot past the entry you just deleted — the very next lookup reports that transaction clean. The fix is a tombstone: a third slot state meaning "occupied once, keep probing".

code

pseudocode · 8 lines
pseudocode
// lookup in a linearly probed, open-addressed table
i = hash(key) mod length(table)
while table[i].state != EMPTY:
    if table[i].state == OCCUPIED and table[i].key == key:
        return table[i].value
    i = (i + 1) mod length(table)
    ...
return NOT_FOUND

go deeper

for a junior

Be ready to say what makes a probe walk stop. Know that a cleared slot is indistinguishable from a never-used one, and that this silently hides other keys stored further along the same path.

for a middle

Explain the three slot states and how the lookup and insert loops read them differently. Trace a two-key collision on a whiteboard to show precisely which lookup breaks and why.

for a senior

Show that the bug is silent and data-dependent: it appears only where a collision existed, so it survives small clean test datasets and surfaces in production as records that mysteriously go missing.

for a principal

Own the argument that a hand-rolled table is only justified when deletion semantics, slot-state accounting and cleanup are designed and tested deliberately. A defect of this shape returns confident wrong answers instead of failing loudly, which is the expensive kind.

## The setting In **open addressing**, every entry is stored directly in the slot array — there are no side lists. When a key's home slot (the slot its hash maps to) is already occupied, the insert walks a **probe sequence**: a deterministic order of slots to try next, the simplest being "the next slot, wrapping around". The key goes into the first slot on that sequence that is free. Because insertion places a key wherever it first found room, the *only* record of where a colliding key went is the probe sequence itself. Lookup re-walks it: start at the home slot, compare, step, compare, step. The walk has to stop somewhere, and the stopping rule is what this whole topic turns on. ## Why an empty slot is the terminator A lookup stops at the first **empty** slot on the path. That rule is sound only because of an invariant maintained by insertion: for every stored key, every slot from its home slot up to its actual position is non-empty. If the walk reaches an empty slot, no key could have been placed past it on this path, so the search can honestly report not-found without scanning the whole table. That invariant is exactly what makes lookups cost a few probes instead of O(n). ## What plain clearing does Writing EMPTY into a deleted entry's slot breaks the invariant for every key whose probe path crosses that slot. Concretely: key A hashes to slot 7 and is stored there. Key B also hashes to 7, finds it taken, and is stored at 8. Delete A by clearing slot 7. Now a lookup for B starts at slot 7, sees empty, and returns not-found — while B still sits in slot 8, invisible. Three properties make this a nasty bug rather than an obvious one: - **It is silent.** No exception, no error, no corrupted memory. The table returns a plausible wrong answer: "that key is not here." - **It is data-dependent.** It only manifests when a collision actually happened, so a test with a handful of well-spread keys passes cleanly and production fails. - **It hides entries you never touched.** The damage is to *other* keys — the ones that collided with the deleted one — not to the key you removed. ## The fix: a third slot state A slot needs three states, not two: EMPTY (never used), OCCUPIED, and DELETED — the **tombstone**. Deleting writes a tombstone rather than EMPTY. The lookup loop then reads two states as "keep going" (OCCUPIED with a non-matching key, and DELETED) and only one as "stop" (EMPTY). The invariant is restored: every slot from a stored key's home to its position is still non-EMPTY, so the walk still reaches it. Storage is cheap — two bits per slot, or a reserved sentinel key that no real key can equal. The real price is paid later: tombstones make probe paths longer for everybody and they do not disappear on their own, which is why load-factor accounting and periodic rebuilds become part of a correct design rather than an optimisation. One shortcut is safe and worth knowing: with linear probing, if the slot immediately after the deleted one is already EMPTY, then no live key was ever probed past this slot, and it can be cleared outright rather than tombstoned. There is also a stronger alternative — repairing the path by shifting later entries backwards — which avoids tombstones entirely but only works when the probe sequence is a contiguous forward scan. ## Different runtimes, different exposure Whether an implementation faces this at all depends on its collision strategy: the built-in dictionaries in Python and Ruby are open-addressed and therefore carry a dummy/deleted marker for exactly this reason, while Java's and Kotlin's standard hash maps resolve collisions with per-bucket chains and can unlink a node on delete without leaving anything behind. Same abstract data type, different deletion problem. ## What interviewers listen for The strong answer names the stopping rule before it names the bug: a candidate who says "the search stops at the first empty slot, and clearing creates a fake empty slot in the middle of a live path" has understood the mechanism. The weak answer is "you have to rehash after every delete" — a real fix, but a wildly expensive one that shows the invariant was never understood.

  • Why doesn't this deletion problem arise when collisions are handled with per-bucket chains?
    Because the bucket head, not the probe path, is what makes an entry reachable. Removing one node leaves the rest of that bucket's nodes reachable from the head, so nothing downstream is orphaned. The failure is specific to open addressing, where the sequence of non-empty slots is the only evidence that a colliding key went further along.
  • What is the minimum you must store to mark a slot as deleted?
    One extra state per slot: EMPTY (never used), OCCUPIED, or DELETED. Two bits, or a reserved sentinel key value no real key can equal, is enough. A single boolean "in use" flag is not sufficient, because the lookup loop must distinguish a deleted slot from a never-used one while the insert loop must distinguish it from an occupied one.
  • If the deleted key never collided with anything, is clearing the slot safe?
    Only if no other key's probe path runs through it, which you usually cannot know cheaply — any key with an earlier home slot may have walked over it. With linear probing there is one cheap and sound test: if the next slot is already EMPTY, no live key was probed past this one, so it can be cleared outright.

A row of numbered lockers where anyone finding theirs taken uses the next free one. Empty one locker and the search for a bag stored just past it gives up at the gap.

saying these in an interview costs you the question

  • Says deletion just writes an empty value into the slot
  • Thinks the lookup scans the whole table anyway
  • Believes only the deleted key is affected
  • Treats a deleted slot and a never-used slot as the same thing
  • Proposes rebuilding the whole table after every single delete

context

resolving links…