3.3.5 · D5Hashing
Question bank — Deletion in open addressing — tombstone markers
Before you start, the vocabulary is all inherited from the parent: Open Addressing, the Linear Probing probe sequence , the three slot states EMPTY / OCCUPIED / DELETED, and the effective load factor . The recap below makes every one of those locally available and visible before you touch a single trap.
Visual recap — the vocabulary you'll test
Figure s02 shows the same chain three ways — correct, broken by naive EMPTY-delete, and repaired by a tombstone — so you can see how search flow changes.
True or false — justify
Every answer must give the reason, not a bare verdict.
Deleting a key by setting its slot to EMPTY is always safe if that key sits at the very END of its probe chain (nothing was inserted after it into that chain).
True — if no key ever probed through this slot, there is no chain to break; EMPTY just restores the original "nothing here" state. But you rarely know this cheaply, so tombstones are the safe default.
A tombstone slot counts as "free space" for the purpose of INSERT.
True — insert may place a new key on a tombstone (it qualifies as "free to write," per figure s03). But it must still scan onward to EMPTY first to rule out a duplicate, so "free" does not mean "stop here immediately."
A tombstone slot counts as "free space" for the purpose of SEARCH.
False — for search a tombstone behaves like OCCUPIED: it says "keep probing." Only EMPTY qualifies as "free to stop." Treating a tombstone as free would make search stop early, the exact bug tombstones exist to prevent.
Tombstones increase the number of live keys stored in the table.
False — they store no key at all. They only inflate , which raises search cost (push up the s04 curve), without adding anything findable.
After rehashing, the effective load factor equals the true live load factor .
True — rehash reinserts only OCCUPIED entries into a fresh array and drops every tombstone, so and .
In Separate Chaining you also need tombstones to delete safely.
False — chaining stores keys in linked lists per bucket, so deletion just unlinks a node; there is no probe chain through the array to break, hence no tombstone needed.
Search cost after many delete/insert cycles depends only on how many real keys are in the table.
False — it depends on , which includes tombstones. A table with few live keys but many tombstones can have long, slow searches.
If a probe sequence contains only OCCUPIED and DELETED slots and never an EMPTY one, an unsuccessful search must probe the entire table.
True — with no EMPTY to stop at, search only halts on finding the key; a missing key forces it to walk every reachable slot. This is why a table saturated with tombstones degrades to O(m).
Spot the error
Each line describes a flawed implementation or claim. Say what breaks before revealing. (Figure s02's middle panel is the picture of the first trap.)
"Delete: find the key, overwrite its slot with EMPTY, done."
Overwriting with EMPTY punches a hole: any key inserted later in that same chain will now be reported missing, because search stops at the new EMPTY (see s02, middle). Use DELETED instead.
"Insert: walk the probe chain; the moment you see a tombstone, drop the new key there and return."
You may have skipped an existing copy of the key sitting further down the chain (it was inserted before the deletion). This creates a duplicate. Remember the first tombstone but keep scanning to EMPTY or the key.
"Search: stop and report 'not found' as soon as you see a DELETED slot."
DELETED must be treated like OCCUPIED for search — the real key may live just past it. Stopping there re-introduces the original deletion bug.
"We never rehash because each delete is O(1), so the table can only get faster over time."
Deletes are O(1) but each leaves a tombstone; accumulated tombstones raise and push search/insert up the s04 curve toward O(m). Periodic rehash is required to purge them.
"When counting toward the rehash threshold, only count OCCUPIED slots; tombstones don't fill the table."
The threshold should track , which includes tombstones — they are exactly what causes the slowdown you rehash to fix. Ignoring them means you rehash far too late.
"Insert found the key already present at slot 8; but we had passed a tombstone at slot 5, so we move the key to slot 5."
If the key already exists, insert should update in place (or do nothing), not relocate it. Moving it needlessly could break other invariants and wastes work; the tombstone is only used when the key is absent.
Why questions
Why is EMPTY the only state that stops a search, while OCCUPIED and DELETED both let it continue?
Because the probe invariant guarantees no EMPTY slot lies between a key's home and its actual position — so the first EMPTY genuinely means "the chain ended, key not here." OCCUPIED and DELETED both mean "the chain may continue," so search must walk past them.
Why does insert get to reuse a tombstone but search must not skip past it?
Insert wants any usable slot and DELETED holds no key, so reusing it is fine (after confirming no duplicate). Search is looking for a specific key, and the key it wants could be beyond the tombstone — so it must keep the chain intact by walking through. This is exactly the "free-for-whom" split in figure s03.
Why does the unsuccessful-search cost formula use rather than the live load factor?
Search walks past both real keys and tombstones alike, so the "fullness" it experiences is the total non-EMPTY fraction , not just the live-key fraction. That is the plugged into the s04 curve.
Why does rehashing, not just "compacting," solve the tombstone problem?
Positions come from ; you cannot slide keys around freely without recomputing their probe paths. Reinserting each live key from scratch into a fresh array recomputes correct positions and naturally omits tombstones.
Why must insert still scan all the way to EMPTY even after it has found a tombstone to reuse?
To guarantee the key isn't already stored further down the chain. Only an EMPTY (or finding the key) proves the chain has truly ended; anything short of that risks a silent duplicate.
Why is deletion trivially cheap in separate chaining but subtle in open addressing?
In chaining a key is a list node you simply unlink, affecting nothing else. In open addressing keys share one array and are linked implicitly by probe order, so removing one can sever the path to another.
Edge cases
Delete a key that is the sole occupant of the table (all other slots EMPTY). Does it need a tombstone?
Strictly no chain runs through it, so EMPTY would be correct — but implementations usually still write DELETED for uniformity; either is safe here.
The table is completely full of OCCUPIED slots (no EMPTY anywhere) and you search for a key that is absent. What happens?
Search probes every slot without ever hitting EMPTY, then reports "not found" — an O(m) worst case (, the far right of the s04 curve). This is why load factor is kept below 1 and rehashing exists.
You delete every key, leaving the array all tombstones and no OCCUPIED slots. Is zero?
No — but , so . Searches are maximally slow despite zero live keys; a rehash resets it to .
You insert a key onto a tombstone: after insertion, what is that slot's state and how do the counts change?
The slot becomes OCCUPIED; rises by one and falls by one, so stays unchanged for that single reuse.
A probe sequence wraps around the array end (slot then slot ) because of the . Do tombstone rules change at the wrap point?
No — makes the sequence circular (see the wrap arrow in figure s01), and EMPTY/DELETED/OCCUPIED are interpreted identically wherever the probe lands. The wrap is invisible to the state logic.
You search for a key and land immediately on EMPTY at (the home slot itself is EMPTY). What do you conclude?
The key is absent — since insert always fills the home slot first if free, an EMPTY home means the key was never inserted here (0 collisions) and no chain exists.
Two different keys hash to the same home slot; you delete the first one. Can the second still be found?
Yes — the first slot becomes DELETED, and search walks past it (treating it like OCCUPIED) to reach the second key further along the chain. That is precisely what the tombstone protects (figure s02, right panel).
Connections
- Parent: tombstone markers — the full derivation these traps test.
- Open Addressing — the setting where implicit probe chains make deletion subtle.
- Linear Probing — the probe rule referenced throughout.
- Load Factor and Rehashing — why drives the rehash decision.
- Separate Chaining — the contrast where deletion is trivially O(1).
- Hash Functions — the every probe chain starts from.