>_ barehands / blog ← Challenges

Why Hash Tables Need Tombstones

Jun 5, 2026

A probe chain stepping over a tombstone left by a deleted key

There are two ways to build a hash table. Chaining gives every bucket a linked list and pushes colliding keys onto it. Open addressing keeps everything in one flat array: if a key's home slot is taken, you probe to the next slot, and the next, until you find space or your key. Open addressing wins on speed in practice because it is cache-friendly: one contiguous array, no pointer chasing, no per-entry allocation. Python's dict, Go's map, and most high-performance tables are open-addressed variants.

It also has a sharp edge that everyone cuts themselves on exactly once, and the cut teaches a genuinely subtle lesson about deletion.

The setup: linear probing

Each slot is EMPTY, USED, or (foreshadowing) something else. Insert hashes the key to a home slot and walks forward until it finds the key or an empty slot. Lookup does the same walk and stops at the first empty slot, because an empty slot means "the probe chain ends here, your key is not present." That stop condition is what makes lookups fast: you do not scan the whole table, you scan until the chain runs out.

Now suppose three keys A, B, C all hash to slot 5. They land in 5, 6, 7. Everything works: looking up C starts at 5, sees A, sees B, sees C, done.

The trap: delete from the middle

Delete B. The obvious move is to set slot 6 back to EMPTY. Now look up C. The probe starts at slot 5 (A), moves to slot 6, sees EMPTY, and concludes "chain ended, C is not here." But C is here, in slot 7. By emptying a slot in the middle of a probe chain, you severed the chain and hid every key after it. Your delete did not remove one key, it silently lost several. This is the bug, and it is nasty because the table looks fine until a specific lookup quietly returns "not found" for a key that is sitting right there.

The fix: a tombstone

Deletion cannot leave an EMPTY slot, because EMPTY is the signal that ends a probe. So it leaves a third kind of marker, a tombstone (TOMB): "something was deleted here, but keep walking."

enum { SLOT_EMPTY = 0, SLOT_USED = 1, SLOT_TOMB = 2 };

bool hm_get(HashMap *m, int key, int *out) {
    size_t h = hash(key) % m->cap;
    for (size_t i = 0; i < m->cap; i++) {
        Slot *s = &m->slots[(h + i) % m->cap];
        if (s->state == SLOT_EMPTY) return false;          // real end of chain
        if (s->state == SLOT_USED && s->key == key) { *out = s->val; return true; }
        // SLOT_TOMB: skip over it and keep probing
    }
    return false;
}

Lookup now treats a tombstone as "not my key, keep going," and only an EMPTY ends the search. The chain stays walkable. Delete B by marking slot 6 TOMB, and looking up C still finds it, because the probe steps over the tombstone instead of stopping at it.

The insert that has to be careful

Tombstones make insertion subtly clever. You want to reuse a tombstoned slot (otherwise deletions slowly fill the table with dead markers), but you also must not insert a duplicate. So insertion remembers the first tombstone it passed, yet keeps probing all the way to an EMPTY slot to be sure the key is not already present further down the chain. If it finds the key, it updates in place; if it reaches EMPTY, it inserts at that remembered tombstone:

// remember the first tombstone, but keep scanning for an existing key
if (s->state == SLOT_TOMB) { if (insert_at < 0) insert_at = idx; continue; }
if (s->state == SLOT_EMPTY) { /* key absent: place at insert_at or here */ break; }
if (s->state == SLOT_USED && s->key == key) { s->val = val; return; } // update

Get that logic right and the table reuses dead space and never inserts a duplicate. Get it wrong and you either leak slots or shadow keys.

The lessons that travel

A flat array, a hash, and a forward walk give you a beautifully fast map. The tombstone is the small, easy-to-miss piece that keeps it correct when keys come and go.

Build it yourself. Solve the Open-Addressing Hash Table challenge on barehands and get graded on correctness and speed. No libraries, just cc -std=c11.

← All posts