Linear Probing and the Arithmetic of Primary Clustering

The simplest probe sequence is the one that tries the next slot, then the one after that. It needs no second hash function, no coprime arithmetic, and no per-key state beyond the starting index. It also has a clustering behaviour that makes its cost formula quite different from the uniform-hashing ideal, and understanding that difference is the price of admission for every faster open-addressed design built on top of it.

The sequence and its immediate consequences

Linear probing maps key k to a probe sequence (h(k) + i) mod m for i = 0, 1, 2, …. Insertion walks forward until it finds a free slot. Lookup walks forward until it finds the key or an empty slot. The array is scanned in index order, so consecutive probes usually land in the same cache line.

The cost of that locality is that collisions are not independent. Suppose two keys hash to slots 4 and 5, and slot 4 is occupied. The key aimed at 5 continues to 6, but so does the key aimed at 4 if it arrived first. Any key whose home slot falls inside an occupied run ends up appended to the end of the run. Runs therefore grow by attracting further keys, and a run of length L occupies L consecutive slots that all behave as a single collision domain.

This is primary clustering: keys that collide at one slot also collide with keys that merely hash near it. Double hashing, which gives each key an independent stride, avoids it, and quadratic probing reduces it, because each key’s offsets diverge from those of a key with a different home slot even when the two home slots are adjacent. Linear probing cannot, because its sequence structure is exactly what creates the runs.

Knuth’s probe counts and what they mean in practice

Under the assumption that the hash function is uniform, the expected number of probes for linear probing is known exactly. An unsuccessful search costs approximately

$$ \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right) $$

and a successful search approximately

$$ \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right) $$

where α is the load factor. Compare with the uniform-hashing formulas 1/(1-α) for a miss and (1/α)ln(1/(1-α)) for a hit. At α = 0.5, uniform hashing predicts 2 probes for a miss and about 1.39 for a hit; linear probing predicts 2.5 and about 1.5. At α = 0.75, the figures are 4 and 8.5 for a miss, 1.85 and about 2.5 for a hit. At α = 0.9, 10 and 50.5 for a miss, 2.56 and 5.5 for a hit.

The growth is quadratic in 1/(1-α) rather than linear. That single change dictates the operating point: linear-probed tables are commonly held at α around 0.5 to 0.7, not at 0.9, and the cost of a miss is the constraint that matters because every insertion of a new key is also an unsuccessful search until it finds its slot.

The practical picture is better than the formula suggests, for a reason the formula deliberately excludes. Probes walk forward through contiguous memory, so a run of eight slots costs about one cache miss on a machine with 64-byte lines, not eight. The formula counts slot inspections; the hardware charges for lines. This is why linear probing outperforms its own asymptotic curve on real workloads and why the design reappears inside modern high-performance tables in modified form, as described in SwissTable probing.

A table that must survive high load factors cannot use linear probing as its only defence. Robin Hood insertion reshapes the distribution of probe lengths without changing the probe sequence, which is covered in Robin Hood hashing.

Deleting without tombstones

Tombstones solve the deletion problem at the cost of accumulating garbage. Linear probing admits a better answer because the probe sequence has a local structure: an entry’s probe path is a contiguous run of indices, so a hole can be repaired by pulling subsequent entries back.

The algorithm, usually called backward-shift deletion, works as follows. Clear the target slot. Then scan forward from it, moving the hole to the next slot whenever the entry there could not be reached without crossing it. The scan stops at the first empty slot, because no entry beyond that point can depend on the hole. Lookups stay short because no marker is left behind, and the cluster closes up rather than accumulating holes.

The interval test is the subtle part. With indices taken modulo m, an entry at index j with home h is displaced across the hole at i when the distance from h to j is at least the distance from h to i. Written cyclically:

/* Is entry at j (home h) reachable only by crossing the hole at i? */
static int crosses(size_t h, size_t i, size_t j, size_t m)
{
    size_t to_hole = (i - h + m) % m;
    size_t to_entry = (j - h + m) % m;
    return to_hole <= to_entry;
}

void erase(struct table *t, size_t i)
{
    size_t m = t->mask + 1;
    t->slot[i].state = EMPTY;
    t->count--;

    for (size_t j = (i + 1) % m; t->slot[j].state == OCCUPIED; j = (j + 1) % m) {
        size_t h = t->slot[j].hash & t->mask;
        if (crosses(h, i, j, m)) {
            t->slot[i] = t->slot[j];       /* pull it back into the hole */
            t->slot[j].state = EMPTY;
            i = j;                          /* the hole moves forward */
        }
    }
}

Each move shifts the hole one step forward, and the loop ends at the first empty slot, which no entry can depend on. The invariant after deletion is identical to the invariant after insertion: every key is reachable from its home slot by a forward scan that stops only at empty slots. No deleted state exists, so no tombstone accumulation and no need for a separate fill counter.

The cost is bounded by the length of the cluster that follows the deleted slot, not by the table size, but a deletion inside a long run moves every entry in that run, so the worst case of one deletion is the worst case of one probe sequence. Deletion is therefore more expensive than in a chained table, where unlinking is constant time. Workloads that delete heavily and rarely look up are better served by chaining.

Choosing the modulus and the hash

Linear probing requires the sequence to visit every slot, which it does for any m, so the modulus is free to be whatever is cheapest. Power-of-two table sizes allow the index to be computed with a bitwise AND instead of a division, and division is among the slower integer instructions. The catch is that the low bits of the hash now determine the slot entirely. A hash function that returns a pointer value, or the result of a multiply that leaves the high bits well mixed and the low bits patterned, will produce systematic collisions. Table hashes must therefore mix downward, which is the subject of hash functions for table indexing.

Prime table sizes avoid that sensitivity and make any reasonably uniform hash usable, at the cost of a modulo on the hot path and a resize sequence that cannot simply double. Implementations that choose primes typically precompute a table of primes near successive powers of two and round the requested capacity upward.

Two edge cases remain. A table that fills completely has no empty slot, so both insertion and unsuccessful lookup loop forever; the growth check must run before the table reaches α = 1, and the search loop should still carry a probe bound as a defensive measure. And a table with a single slot is legal but degenerate: any second key forces a resize, which is why implementations start at a small but nonzero capacity.

Linear probing is the design that trades theoretical probe count for physical locality and simplicity. Its weaknesses are known, quantified, and fixable by changing the insertion rule rather than the probe rule, which is why the interesting variants of open addressing are mostly variants of how a collision is resolved rather than where the probe goes next.