Open Addressing, Probe Sequences, and the Cost of Deletion

Separate chaining answers a collision by adding a node to a list. The alternative is to answer it by trying another slot. That single change removes every pointer from the structure: keys and values live in one flat array, and the array index is the only place a key can be. The cost is a rule that must be defined before anything else works, namely which slot to try after the first one, and a deletion problem with no clean solution.

The probe sequence contract

An open-addressed table is an array of m slots, each either empty, occupied, or deleted. A hash function produces an initial index, and a probe sequence is a permutation of the slot indices derived from the key. Lookup computes the sequence and visits slots in order: if a slot holds the key, the search succeeds; if it is empty, the key is absent and the search stops; otherwise the search advances.

Insertion follows the same walk but stops at the first slot that is empty or deleted, and claims it. That is the entire mechanism. The load factor α = n/m must stay below 1, because a table where every slot is occupied has nowhere to put a new key and every unsuccessful lookup would run forever.

The guarantee that makes termination possible is that the probe sequence is a permutation: it visits every slot exactly once. Without that property a key could be absent while the walk revisits a subset of slots and never reaches the empty one that would prove absence.

Three families of probe sequence are standard. Linear probing uses successive offsets, (h(k) + i) mod m. Double hashing uses a per-key stride, (h₁(k) + i·h₂(k)) mod m, which requires the stride to be coprime with m. Uniform hashing, the theoretical ideal, picks a random permutation for each key, and no real implementation does it, but it supplies the cost model that the others are measured against.

Cost of a probe under uniform hashing

Under uniform hashing, an unsuccessful search examines slots that are occupied with probability α, independently. The expected number of probes is the sum of a geometric series:

$$ \sum_{i \ge 0} \alpha^{i} = \frac{1}{1-\alpha} $$

A successful search averages over the keys present, giving approximately (1/α)·ln(1/(1-α)) probes. Both expressions are Θ(1) while α is bounded away from 1 and both blow up as α approaches it.

The numbers are worth internalizing because they explain the design margins. At α = 0.5 an unsuccessful search averages 2 probes and a successful one about 1.39. At α = 0.75, 4 and about 1.85. At α = 0.9, 10 and about 2.56. The unsuccessful case degrades much faster than the successful one, which is why tables that must answer negative queries, such as a cache or a set used for filtering, are kept looser than tables that mostly hit.

The comparison with chaining is a memory argument, not a time argument. At equal α the two families have similar expected probe counts. But a chained table pays a pointer plus allocator overhead per key, while an open-addressed table pays one slot per key and no per-key allocation at all. For small keys the difference is a factor of several in memory, and memory is what determines whether the working set fits in cache.

Deletion and the tombstone

Removing a key from an open-addressed table breaks the probe invariant if done naively. Clearing the slot to empty would cause any lookup whose probe sequence passed through that slot to stop early and report absence for a key that is still further along the sequence.

The standard fix is a third state. The slot is marked deleted, or a tombstone is written into it. Lookup treats a tombstone as “continue”, so the walk does not terminate; insertion may reuse it. The table remains correct, but tombstones accumulate, and a probe sequence that crosses many of them does the same work as one that crosses occupied slots.

Accumulated tombstones degrade performance in a way that is invisible to a load factor computed from live keys alone. An implementation must therefore track a second quantity, the fraction of slots that are neither empty nor free, and rebuild when that fraction crosses a threshold even if few live keys remain. CPython’s dictionary marks a deleted entry with the dummy sentinel object and triggers a rebuild when the slot count reaches two-thirds of capacity, counting every slot that is neither empty nor the dummy.

The alternative is backward-shift deletion, which repairs the probe chain instead of marking it. When the slot at index i is vacated, the algorithm scans forward and moves any entry whose home position lies cyclically between the vacated slot and its current slot back into the hole, repeating until it reaches an empty slot. No tombstone is created and lookups stay short. The catch is that the repair is only well defined when the probe sequence has the special structure of linear probing, and the scan can be long. That method is described in linear probing.

A minimal table with tombstones makes the three-state logic explicit:

enum state { EMPTY, OCCUPIED, DELETED };
struct slot { unsigned long hash; const char *key; enum state st; };

/* Returns 1 if found; on miss, *put is the slot an insert should claim. */
int probe(struct slot *tab, size_t m, unsigned long h, const char *key, size_t *put)
{
    size_t first_free = SIZE_MAX;
    for (size_t i = 0; i < m; i++) {
        size_t j = (h + i) & (m - 1);          /* linear; m is a power of two */
        if (tab[j].st == EMPTY) {
            *put = (first_free != SIZE_MAX) ? first_free : j;
            return 0;
        }
        if (tab[j].st == DELETED) {
            if (first_free == SIZE_MAX) first_free = j;
            continue;                           /* keep walking: key may be further on */
        }
        if (tab[j].hash == h && strcmp(tab[j].key, key) == 0) {
            *put = j;
            return 1;
        }
    }
    *put = first_free;                          /* table full of live + deleted slots */
    return 0;
}

The first_free variable is the detail that separates a correct insert from a table that slowly fills with tombstones. An insertion that stops at the first tombstone it crosses may overwrite a slot that lies before the key’s true position, and a later lookup for the displaced key would then terminate at the wrong empty slot. Recording the earliest reusable slot while continuing the search preserves both properties: the search still proves absence correctly, and the insertion reuses space without extending any chain.

Where the invariants break

Three assumptions do the work above, and each fails somewhere.

The first is that the probe sequence covers every slot. Linear probing with a power-of-two table and odd stride satisfies it. Double hashing satisfies it only when the stride is coprime with the table size; if both share a factor, the sequence is confined to a subset of slots and an insertion can fail on a table that is not full. Implementations either choose a prime table size and a stride in [1, m-1], or force the table size odd and the stride odd.

The second is that keys are comparable without moving them. Open addressing compares the stored key in place. When keys are large strings or structures, each probe is a cache miss plus a comparison over the whole key. Storing a cached hash alongside the slot lets the comparison reject almost every candidate on an integer test, which is why most implementations keep the full hash in the slot rather than recomputing it.

The third is that growth can be done by rehashing. Because keys live in the array, a resize must reinsert every one of them, at Θ(n) cost. That cost is amortized by geometric growth, but it lands as a single long pause. Spreading it across operations is the technique in incremental rehashing.

None of this changes the asymptotic story: open addressing gives expected O(1) operations with the smallest possible constant memory per key, provided the table is kept below a load factor its probe sequence can tolerate. Choosing the sequence is where the real engineering is, and the simplest choice has a clustering problem that is easy to see and hard to avoid.