With every key inside the table, a search stops at the first empty slot — so a deletion that empties a slot cuts every probe chain running through it, and keys already in the table become unreachable. The lab names them. Linear probing also clusters, which makes an unsuccessful search cost about ½(1 + 1/(1−α)²) rather than 1 + α: an approximation, printed beside probes that were counted.
Core ideas
Three ideas, and the second is the one that costs people a data-loss bug: in a probing table a deletion is not the opposite of an insertion.
A key does not live at h(k); it lives at the first slot in its probe sequence h(k), h(k)+1, h(k)+2, … that was free when it arrived. A search re-walks that sequence and stops at the first empty slot, because an empty slot means the key would have been put there. Everything about probing follows from that stopping rule, including the deletion problem.
Emptying a slot creates a stopping point in the middle of other keys’ probe sequences, and every key beyond it becomes unreachable — still in the table, never found again. The fix is a tombstone: a slot marked dead, which a search walks past and an insertion may reuse. The lab deletes eight keys from a table of twenty-two and reports which three of the survivors go missing when the mark is omitted.
Occupied slots gather into runs, and a long run is more likely to catch the next key, which makes it longer. Chaining has no such effect: its chains are independent. So the expected unsuccessful search is not 1 + α; the standard analysis gives about ½(1 + 1/(1−α)²), which blows up as α approaches 1 — and with everything inside the table, α cannot exceed 1 at all.
The material
The probe rule, the tombstone rule with the keys that go missing without it, and the approximation printed beside the counts.
Every key is stored in a slot of the table itself; there are no chains. A key k has a probe sequence h(k, 0), h(k, 1), … covering all m slots. Insert walks it to the first free slot. Search walks it and stops when it finds k or reaches an empty slot. Since every key occupies a slot, n ≤ m and so α ≤ 1.
Linear probing is h(k, i) = (h(k) + i) mod m: try the next slot, and the next. Double hashing uses a second hash function for the step, which breaks up the runs.
The lab offers only power-of-two table sizes, and the reason is worth knowing: the double-hashing step it computes is always odd, and an odd step is coprime with m — so the probe sequence reaches every slot — exactly when m is a power of two. At m = 13 a step could share a factor with the table size and the sequence would miss slots, which is a silently broken table rather than a slow one.
Search stops at the first empty slot. So consider a key k whose probe sequence is 5, 6, 7 and which ended up in slot 7 because 5 and 6 were taken. Delete the key in slot 6 by emptying it, and now a search for k probes slot 5, probes slot 6, finds it empty, and reports that k is not in the table. k is in slot 7. It will never be found again.
A slot may be empty, occupied, or dead — a tombstone left by a deletion. A search treats a dead slot as occupied by something else and keeps going; an insertion treats it as free and may reuse it. Only an empty slot stops a search.
The cost is that tombstones accumulate: they lengthen searches without holding keys, so a table with many deletions eventually needs rebuilding even though its load factor looks healthy.
The lab fills a table of 32 slots with 22 keys, deletes eight of them and then searches for the fourteen that remain. With tombstones, all fourteen are found. Deleting by emptying the slot instead loses three of them, and the panel prints their keys. Nothing about the table looks wrong: the load factor is right, the slots are consistent, and three records are gone.
Now the cost. A table of 32 slots aimed at seven tenths full ends up with 22 keys, so α = 11/16 = 0.6875. The lab then searches for twelve keys that are not present and for all 22 that are, counting probes, and prints the standard curves beside the counts:
Those two right-hand numbers are the one approximation this lesson prints, and what is approximate is the model, not the arithmetic. Knuth’s curves assume a uniform hash function and the idealised distribution of cluster lengths the analysis derives, and this library proves neither. The numbers beside them were produced by walking 32 slots and incrementing a counter. The lab labels the column, and the reason to keep the two apart is visible one row down the load curve.
At α = 7/8 the curve says 32.5 and the table counted 8.4. Neither number is wrong. The curve describes a table large enough for the idealised cluster distribution to hold; a 32-slot table at α = 7/8 has four empty slots, and an unsuccessful search stops at one of them after about eight probes. The curve is asymptotic in m as well as in the load, and the lab prints the difference in its own column so the parting of the two is on the page rather than in a footnote.
Above α = 0.98 the lab refuses to print the curve at all, and says so where the number would have been. The reason is that the curve is effectively vertical there: 1/(1−α)² is 2500 at α = 0.98 and 10 000 at 0.99, so a figure read off it is a statement about the formula rather than about any table. That refusal is the honest behaviour for a model outside its range, and it is why α in a probing table is kept well below 1 — at α = 1 there is no empty slot left to stop any search at all.
Interactive
Every probe is counted; the curve beside the count is an approximation
Method
Insert, search, delete, in that order, and keep the three slot states straight throughout — the whole lesson lives in the difference between empty and dead.
h(k), then h(k)+1, then h(k)+2, modulo m. A key is at the first free slot along that walk, which is often not its home slot, and a search that only checks the home slot finds almost nothing.
Occupied and not the key: keep going. Dead: keep going. Empty: stop and report absent. Those three rules are the structure’s entire correctness argument, and confusing the last two is the bug.
Set the slot dead. Then look at what a search for the keys after it now does — it walks past, as it must. Keep a count of the dead slots: they cost search time and hold nothing, so past a few they are a reason to rebuild the table.
The counts come from the table on screen. The curve comes from a model of an idealised large table, and the lab says so. When they disagree by a lot, ask which assumption of the model this table violates before suspecting either number.
Small enough to hold in your head. Linear probing, h(k) = k mod 8, and the keys arriving in the order shown.
Three keys lost from a five-key table by one deletion, and every one of them is still sitting in the slot it was put in. This is the failure the tombstone exists to prevent, and it is worth doing by hand once because the bug it produces in a real system is a record that cannot be found rather than a crash.
The marked version walks past slot 3 and finds everything. It also shows the cost: searching for 26 now costs three probes forever, one of them spent on a slot that holds nothing. Tombstones trade a correctness bug for a slow leak, and the leak is fixed by rebuilding, which is the next lesson’s subject.
For a faded rehearsal, use the lab at m = 32 with double hashing at the same load. The supplied observation is that the load factor is identical to linear probing’s — 11/16 — and Knuth’s linear-probing curve is therefore unchanged at 5.62. Count the probes: the lab reports 3.000 unsuccessful against linear probing’s 5.000, and the longest cluster drops from 12 to 8. Then say which of those four numbers are counts and which is a model.
You should be able to insert and search along a probe sequence by hand, name the keys a delete-by-emptying loses on a small table, state the three slot states and what each does to a search, and say of any figure on the page whether it was counted or read off a model whose assumptions are not proved here.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.