Tombstones Are Good for You

Linear probing is the simplest hash table there is. Hash the key to a slot; if it's taken, try the next one, and the next, until you find room. It is also famous for one weakness, primary clustering: occupied slots clump into long runs, and every new key that lands in a run has to walk to its end and make it longer. Knuth worked out the cost in 1963. With a table that is a fraction 1 − 1/x full, inserting a key touches about ½(1 + x²) slots. At 75% full that's 8.5. At 98.4% full it's about 2,000.

The usual advice for deletions goes the same way. Don't leave tombstones (markers that say "something was here, keep looking"), because they clog the table; shift the later keys back instead, so the table looks as if the deleted key had never been inserted. A 2021 paper by Bender, Kuszmaul and Kuszmaul, "Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering", argues the opposite. In a table that keeps churning (keys deleted and new ones inserted), tombstones break up the runs, insertions get asymptotically cheaper than Knuth's formula, and if you plant extra tombstones on purpose you can get rid of primary clustering entirely. They call that version graveyard hashing. It's a proof, not a benchmark, so I simulated it to see how big the effect is at sizes you'd actually use.

The setup

A table of about a million slots (2²⁰) filled to 1 − 1/x for x from 2 to 64, so 50% up to 98.4% full. Then the table hovers: delete a random key, insert a new random one, over and over. Two million of those to settle, then a million more to measure, three seeds per setting. The cost of an operation is the number of slots it touches.

The paper uses ordered linear probing, an old variant where keys within a run are kept sorted by hash. A lookup can then stop as soon as it reaches a key with a bigger hash, so even a lookup for a missing key doesn't walk the whole run. An insert finds where the key belongs and shifts the rest of the run right by one, until it reaches an empty slot or a tombstone, which it reuses. Tombstones keep their hash, so they stay in sorted order too. I compared five ways of handling deletes:

• No tombstones. Delete by shifting later keys back (backward shift). The table stays exactly like a freshly built one.
• Tombstones, classic rebuilds. Leave a tombstone, and every n/(2x) inserts rebuild the table without them (n is the number of slots). That's the textbook rebuild interval.
• Tombstones, rebuilt 16× less often.
• Tombstones, never rebuilt.
• Graveyard hashing. Rebuild every n/(4x) operations, and at each rebuild plant n/(2x) fresh tombstones, evenly spaced, for future inserts to use.

First, a sanity check. A freshly filled table and the no-tombstone table under churn both match Knuth's formulas: at 93.8% full (x = 16), finding a key touches 8.5 slots against a predicted 8.5, and inserting touches 130 against 128.5.

Result: inserts get much cheaper, lookups barely notice

Classic tombstones, the thing you're told to avoid, make inserts about 3× cheaper than the clean table at 98.4% full, and missing-key lookups cost 37 slots instead of 34. Graveyard hashing makes inserts 16× cheaper, and its lookups cost about twice as much (65), since the planted tombstones take up room.

The slopes are the more interesting part, because they say what happens as the table gets fuller. Between 93.8% and 98.4% full, the insert cost grows like x^2.0 with no tombstones (Knuth), like x^1.6 with classic tombstones, and like x^1.0 with graveyard hashing. The paper proves x^1.5 times slowly growing log factors for the classic case and x for graveyard, so the simulation lands where the math says it should. Graveyard inserts cost about 2x at every fill level I tried, and lookups about x: primary clustering is just gone.

Rebuild timing is a real dial. Rebuilding 16× less often lets more tombstones pile up between rebuilds, so inserts get cheaper (394) but lookups get slower (58). Never rebuilding is the case the folklore is right about. Its inserts only beat the clean table at 96.9% full and above (at 93.8% they cost 173 against 130), and its lookups end up ~20× worse than the clean table's, since every deleted key leaves a permanent marker that searches have to step over.

Two costs the headline hides

Rebuilds aren't free. A rebuild re-sorts the table in one pass over every slot, about n slot visits. Spread over the inserts between rebuilds, that's 2x visits per insert for classic rebuilds and 8x for graveyard hashing (counted per insert: the graveyard interval counts deletes too). At x = 64 that's 128 and 512, the last column above. A sequential sweep is much cheaper per slot than a probe on real hardware, and it's still linear in x, so graveyard keeps its lead (135 + 512 against 2,158), but the 16× becomes something more like 3× once you count it.

It depends on the ordering. I first ran the same thing on plain linear probing, where a run isn't sorted and a lookup for a missing key has to walk to the first truly empty slot. Tombstones still make placing a key cheap: at 98.4% full, graveyard placement touched about 85 slots against about 1,900 with no tombstones. But a real insert usually has to check first that the key isn't already there, and that check is a missing-key lookup, which now steps over every tombstone. It cost about 7,500 slots with graveyard hashing and about 2,600 with tombstones rebuilt every n/x inserts, both worse than the ~1,900 of the tombstone-free table. On plain linear probing the trick only pays if you know the key is new and can skip the check.

• In a churning table that's ordered by hash, tombstones break up primary clustering. At 98.4% full, classic tombstones make inserts ~3× cheaper and graveyard hashing ~16× cheaper (before rebuild sweeps) than deleting with backward shift, with lookups 1–2× the cost.
• The insert cost grows like x², x^1.6 and x respectively, matching the paper's bounds.
• Never rebuilding is still a bad idea, and on plain (unordered) linear probing tombstones make checked inserts worse, not better.

Limits: one table size, random hashes (an ideal hash function), a workload that alternates one delete and one insert, and cost counted in slots rather than measured in nanoseconds. Real tables have cache lines that make a 4-slot walk nearly free and SIMD tricks that change what a "probe" costs, so the ratios won't transfer one to one. I counted lookups as a search and left out the shifting cost of backward-shift deletes, which slightly flatters the no-tombstone table. At 98.4% full single runs vary a lot (the three no-tombstone seeds averaged 2,158 against Knuth's 2,048), so read the big numbers to about ±10%.