This note explains a general deletion and search principle for linear probing with tombstones. Attempt the exercises before reading the worked explanation below.
Why a deleted slot cannot simply become empty
A hash function chooses a home slot, but collisions require a rule for finding another slot. In linear probing, a table with slots numbers them .
Definition 5.2.1
(Probe sequence)
For a key whose home index is , the probe sequence is
The -th probe, counting from , inspects slot .
This sequence visits every slot exactly once, including when is not prime. It is therefore essential to stop after at most probes, even if every slot is live or deleted.
Definition 5.2.2
(Slot states)
Each slot has exactly one of three states: never used, live with a key and value, or deleted (a tombstone).
Never used and deleted both lack a live entry, but they have different meanings for searching. A live key is found at its matching slot; a deleted slot tells us to continue; a never-used slot proves absence, provided the table has been maintained by the rules below. If no decision occurs earlier, the full probes prove absence.
Insertion, deletion, and duplicate keys
Definition 5.2.3
(Search, insert and delete with tombstones)
Each operation follows the probe sequence of its key for at most probes.
- Search. Stop at the first live slot holding and return its value. Stop with "absent" at the first never-used slot, or after probes. Pass over tombstones and over live slots holding other keys.
- Insert. Remember the first tombstone encountered, but keep probing. If the key is live, update its value at that slot. If a never-used slot is reached, is absent: place it at the remembered tombstone if there is one, otherwise at that never-used slot. If all probes find neither nor a never-used slot, place it at the remembered tombstone; if there was none, report that the table is full.
- Delete. Search first. If the key is found, mark its slot deleted; if it is absent, leave the table unchanged.
Using the earlier tombstone immediately, without finishing the scan, could create a duplicate of a key that is live further along the path. A full table can still update an existing key. A tombstone preserves the search path for any live key whose probe path passes through the deleted slot. Rebuilding the table into fresh slots can remove tombstones, provided every live entry is reinserted correctly.
Worked trace: wraparound and an update
Worked example 5.2.4
(Wraparound, a tombstone and an update)
Let and for these nonnegative integer keys. Insert , and into a new table. All three have home index ; they occupy slots , respectively. Delete key , leaving a tombstone at .
| Operation | Slots inspected in order | Result |
|---|---|---|
| Search for 17 | 5, 0, 1 | Found at 1; the tombstone at 0 does not end the search. |
| Insert 17 with value C | 5, 0, 1 | Update slot 1; do not insert a second 17 at 0. |
| Insert 23 with value d | 5, 0, 1, 2 | Slot 2 is never used, so 23 is absent; reuse the first tombstone at 0. |
After these operations, slots hold keys respectively; slots are still never used. Notice that the last insertion probes beyond the eventual destination because it must first rule out an existing copy of .
Counterexample mode
Deleting by making the slot never used
Suppose deletion of in the trace above wrote "never used" into slot instead of a tombstone. The table now has live entries at slot and at slot . A search for probes slot (a different key), then slot , which is never used, and stops with "absent". But is live at slot , so the answer is wrong. The same table also makes a later insert of place a second copy at slot .
The failure is exactly the violated invariant of the next section: slot lies on the probe path of before its stored slot, and it was never used. Deletion must write a tombstone, which a search passes over, so that no never-used slot ever appears on a stored key's path.
Worked example 5.2.5
(A table with no never-used slot)
Let and . Insert : they go to slots , so the table is full of live slots. Updating the value of probes slots and succeeds even though the table is full. Inserting a new key probes , finds no match, no never-used slot and no tombstone, and reports that the table is full.
Now delete , leaving a tombstone at slot . Insert : it probes slot (key ), slot (the tombstone, remembered) and slot (key ). All probes are done without meeting a never-used slot or the key , so is absent and goes to the remembered tombstone at slot . A search for the absent key , with home slot , now probes , and the bound of probes is what ends it.
Worked example 5.2.6
(Tombstones make an unsuccessful search long)
Let and . Insert into slots , then delete and . Only key remains live. Search for , whose home slot is : slot holds a different key, slots and are tombstones, and slot is never used. The search therefore makes four probes before reporting absence, although only one entry is live. Repeated insertions and deletions can leave tombstones in most slots, and then an unsuccessful search can approach probes. Rebuilding into fresh slots resets the count.
Common mistake
(Inserting at the first tombstone without finishing the scan)
In the first trace, insert again with value , but place it at the first tombstone, slot , as soon as that tombstone is seen. Slots and now both hold a live . Deleting finds slot first and turns it into a tombstone; a search for then passes it and finds the old entry at slot . The deleted key reappears with its stale value. The scan must continue until the key is found or absence is certain, and only then may the tombstone be used.
Common mistake
(Probing without a bound)
With the full table of the second example, searching for and stopping only at a never-used slot never stops: there is none, so the probe index wraps around forever. The rule "stop after at most probes" is part of the algorithm, not an optimization. The same bound limits insertion, which in a table with no never-used slot must stop after probes.
Why the stopping rule works
Assume the table starts entirely never used, and all updates follow the rules above.
Proposition 5.2.7
(Invariants of linear probing with tombstones)
After any sequence of searches, insertions and deletions from a table that begins entirely never used, the following hold.
- Each key occurs in at most one live slot.
- If key is live at slot , then no slot on the probe path of from its home slot up to, but not including, is never used.
Proof
(Never-used slots only disappear)
Initially there is no live slot, so both statements hold. We show that each operation preserves them.
Searching changes nothing. Updating the value of a live key changes no slot state. Deletion changes one live slot into a tombstone. The key held there is no longer live, so no condition about it remains, and every other live key keeps its slot and its path, whose slots have the same never-used states as before.
For insertion of , first suppose is already live. The scan reaches its slot, the value is updated, and nothing else changes. Otherwise the scan finds no live copy of on the part of the path it covers. It ends at the first never-used slot, or after the full cycle of slots. In both cases it has inspected every slot of the path before the chosen one, and a live copy of could not lie beyond the first never-used slot (second invariant) or outside a full cycle. So is absent, and placing it in one slot gives at most one live copy. The chosen slot is the first tombstone passed, or the never-used slot where the scan ended. Every slot before it on the path was inspected and was not a never-used slot, because the scan would have stopped there. So the second condition holds for .
Finally, placing turns a tombstone or a never-used slot into a live slot. The number of never-used slots can only fall, and no tombstone or live slot ever becomes never-used again. A key whose path avoided never-used slots before its stored slot therefore still avoids them. Hence both statements persist.
Proof X-ray
Why a tombstone is not a never-used slot
The invariant that makes search correct is monotone: the set of never-used slots only shrinks, because insertion fills slots and deletion writes a tombstone rather than a never-used state. A condition of the form "no never-used slot before my slot" can then only be helped by changes, never broken. Uniqueness, on the other hand, rests on a different ingredient: insertion scans until it can prove the key absent before it writes anything, so the first tombstone is only a candidate. Take away the first ingredient and deletion could erase a key's path, as in the counterexample; take away the second and an update could be duplicated. Rebuilding into fresh slots is safe for the same reason: it starts from a table with no live slot and reinserts by the same rules.
Proposition 5.2.8
(Correctness of search)
Under the invariants, a search for inspects at most slots. It returns the value of if is live in the table, and reports absence if it is not.
Proof
(The scan cannot step over a live key)
At most probes are made by the rule. Suppose is live at slot . By the second invariant, no slot on the path before is never used, so the search cannot stop early with "absent". It passes only tombstones and slots holding other keys, and by uniqueness the first matching live slot is . So it reaches and returns the value there.
Suppose is not live. No probe finds a matching live slot, so the search ends only with "absent", at the first never-used slot or after probes. In neither case has it missed a live copy, since there is none.
These conclusions depend on the maintained invariant; an arbitrarily corrupted table need not satisfy it.
Concept lensGeometric
The invariant read on a circle
Place the slots on a circle in index order. If some slot is never used, the never-used slots cut the circle into arcs. The second invariant says that each live key lies on the same arc as its home slot , at or after when moving in the direction of increasing index. A search starting at therefore cannot reach a cut before it reaches . If no slot is never used, the arc is the whole circle, and the bound of probes plays the role of the cut.
Cost and exercises
One operation takes at most probes, so its worst-case probe cost is ; a table with slots uses slot storage. Many tombstones can make an unsuccessful search long even if few entries remain live. A general expected constant-time claim needs extra assumptions on hashing and occupancy; it does not follow solely from the existence of a hash function.
Quick check
(With and , insert 3, 7 and 11, then delete 7. Give the slots inspected when searching for 11 and explain why the first deleted slot cannot end the search.)
Solution · Answer
Key goes to slot , key has home slot and goes to slot , and key has home slot and goes to slot , after finding slots and occupied. Deleting leaves a tombstone at slot . Searching for inspects slots and finds it at slot . The tombstone at slot records only that some key once stood there, and was placed beyond it when slot was occupied. If the search stopped at the tombstone, it would wrongly report absent.
Quick check
(Suppose every slot is either live or deleted and no live slot has key . Describe how to insert both when a tombstone exists and when none exists. Why must the scan be bounded?)
Solution · Answer
With a tombstone, scan all slots without finding , remembering the first tombstone met, and insert there. With no tombstone, every slot is live and holds another key, so the table is full and the insertion is reported as failing. The scan must stop after probes because there is no never-used slot to end it; without the bound the probe index would wrap around forever.
Quick check
(Explain why inserting immediately at the first tombstone can violate key uniqueness. Construct a short example with a later matching live key.)
Solution · Answer
The tombstone says nothing about whether the key is already live further along its path. Take , and insert : they occupy slots . Delete , leaving a tombstone at slot . Inserting again at the first tombstone puts a second live at slot , ahead of the old one at slot . Two live slots now hold the key , so the first invariant fails. A correct insertion continues to slot , finds live, and updates it.