Probe Sequences in Open-Addressed Hash Tables

A chained hash table stores colliding keys in a list hanging off each slot. Open addressing stores them in the table itself: one key per slot, no pointers, and a collision resolved by trying a different slot according to a deterministic sequence. The absence of pointers is what makes the technique attractive — a slot holds a key and a value, nothing else — and the sequence is what determines whether the table behaves well or collapses into a linear scan.

The probe sequence is the algorithm

Every open-addressed table is defined by a function that, given a key’s hash and a probe number, produces a slot index. Lookup recomputes the same sequence and stops at the first slot that is empty (key absent) or that holds the key (found). Insertion writes to the first empty slot in the sequence. Everything else — clustering behaviour, cache behaviour, the cost of deletion — follows from the choice of sequence.

The three families in use differ in what they guarantee about the sequence.

Linear probing uses (h(k) + i) mod m for probe i. Consecutive probes are adjacent slots, so a probe sequence is a contiguous run and the hardware prefetcher sees a predictable stream. The weakness is that two keys whose hashes collide have identical sequences from that point on, and any key whose hash falls into an occupied run joins the run. Runs grow and merge, and the cost is not the collision probability of a single key but the length of the run it lands in.

Quadratic probing uses (h(k) + c₁i + c₂i²) mod m, most commonly with the triangular sequence h(k) + i(i+1)/2. It avoids the contiguous-run problem but introduces a weaker one: keys with the same initial hash still follow the same sequence, so they collide repeatedly at every probe. The standard choice of m a power of two and the triangular sequence has a useful property — the sequence visits every slot exactly once before repeating, because the triangular numbers modulo 2^j are a permutation.

Double hashing uses (h₁(k) + i·h₂(k)) mod m, which gives each key its own step size and therefore its own sequence. It is the closest an open-addressed scheme gets to the ideal of uniform independent probes. The requirement is that the step be coprime with the table size, or the sequence visits only a subset of slots. With m a power of two, the step must be odd; with m prime, any nonzero step works.

The idealised analysis assumes every probe is uniformly random among the unvisited slots. Under that assumption, an unsuccessful search at load factor α makes an expected 1/(1 − α) probes, and a successful search makes (1/α)·ln(1/(1 − α)). At α = 0.5 those are 2.0 and 1.4; at α = 0.9 they are 10.0 and 2.6. The divergence between the two columns is the reason load factor, not table size, is the number that matters: unsuccessful searches (insertions, misses) degrade as 1/(1−α), while successful ones degrade only logarithmically.

Linear probing is far worse than the ideal at high load, and the exact penalty is known. Knuth’s analysis of the parking problem gives an unsuccessful search an expected ½(1 + 1/(1 − α)²) probes; the successful-search figure, ½(1 + 1/(1 − α)), is the older and slightly optimistic estimate and understates the cost at high load. At α = 0.9 the unsuccessful formula gives 50.5 probes against the idealised 10.0. At α = 0.5 it gives 2.5 — close enough to the ideal that linear probing’s cache advantage dominates.

Clustering, and the two kinds of it

Primary clustering is the linear-probing pathology: occupied slots form runs, a new key landing anywhere in a run extends it by one, and a key landing just before a run joins it. The probability that a slot begins a run of length t falls off geometrically, but the expected run length grows without bound as α approaches one. The practical consequence is a hard cliff: a linear-probing table at α = 0.5 behaves well, at α = 0.75 it is noticeably worse, and at α = 0.9 it is unusable for misses.

Secondary clustering is the quadratic-probing pathology: keys that share an initial hash follow identical sequences, so they pile onto the same slots at every probe even though those slots are not adjacent. It is milder than primary clustering — the sequences are spread out — but it cannot be removed without giving each key its own sequence, which is what double hashing does.

Double hashing’s cost is arithmetic and cache behaviour. Each probe computes a multiplication and a modulo, and each probe lands at a pseudo-random distance, so a probe sequence touches a different cache line every time. On a table that fits in cache this does not matter much; on one that does not, each probe is potentially a miss, and the 1/(1−α) bound is multiplied by a hundred-cycle latency. This is why linear probing remains popular despite its worse probe counts: three probes in one cache line beat one probe in a random line.

Deletion is where implementations break

An open-addressed table has no way to mark a slot as empty without breaking lookups for keys that probed past it. If a key is removed and the slot is cleared, a lookup for a key that was inserted later in the same run will stop at the cleared slot and report a miss. Two mechanisms exist.

Tombstones. The deleted slot is marked with a distinct state, neither empty nor occupied. Lookup continues past tombstones; insertion may reuse one. The problem is accumulation: a table that sees many deletions fills with tombstones that are not keys but still occupy the probe path, so the effective load factor rises even though the count of live keys falls. The usual mitigation is to count tombstones toward the load factor and rehash when the combined count crosses a threshold, which makes a delete-heavy workload pay for periodic rebuilds.

Backward-shift deletion. Instead of marking, the deletion removes the hole by shifting subsequent entries back into it, stopping when it reaches an empty slot or an entry that is at its home position. This keeps the table free of tombstones and preserves the invariant that a lookup stops at the first empty slot. It is only correct for linear probing, because it relies on the probe sequence being a contiguous run: the entry at slot j may be shifted to j − 1 only if j − 1 is in its probe path, which for linear probing means checking whether the entry’s home slot lies cyclically between j − 1 and j.

/* Remove key from a linear-probing table; keys are nonzero, 0 means empty.
   Shifts later entries back so no tombstone is needed. */
void delete_linear(long *tab, size_t m, long key)
{
    size_t i = (size_t)key % m;
    while (tab[i] != key) {                 /* caller guarantees presence */
        if (tab[i] == 0) return;
        i = (i + 1) % m;
    }
    size_t j = i;
    for (;;) {
        j = (j + 1) % m;
        if (tab[j] == 0) { tab[i] = 0; return; }
        size_t home = (size_t)tab[j] % m;
        /* Shift only if home is not cyclically within (i, j]. */
        int movable = (i <= j) ? (home <= i || home > j)
                               : (home <= i && home > j);
        if (movable) { tab[i] = tab[j]; i = j; }
    }
}

The movable test is the whole subtlety. Without it, a key whose home slot is outside the gap would be moved ahead of its own probe start and become unreachable. The cyclic comparison has two cases because the gap can wrap around the end of the table, and getting the wrap wrong produces a table that works until the first deletion near index zero.

Robin Hood, and what ordering the run buys

Robin Hood hashing keeps linear probing’s contiguous runs but changes the insertion rule: when an incoming key has probed further from its home slot than the entry currently occupying the slot, the two swap and the displaced entry continues probing. The effect is to equalise probe lengths. A key that was lucky enough to land near its home gives up its position to a key that has travelled far.

The invariant is that entries in a run appear in non-decreasing order of their probe distance. Two consequences follow. Lookup can stop early: if the current slot’s probe distance is less than the distance the query has already travelled, the query’s key cannot be further along, because it would have displaced the entry it is now comparing against. And the distribution of probe lengths becomes tightly concentrated: Celis’s analysis shows that the mean successful-search cost stays near a small constant — about 2.6 probes — even as the load factor approaches one, and that both the mean and the variance are bounded, against a spread in plain linear probing where a few keys travel far further while the mean stays similar. The improvement is in the tail, not in the mean.

The variance reduction is the point. In plain linear probing, the average probe count is the number that analysis reports, but the operation that hurts is the worst one, and the worst one is far above the average. Robin Hood does not reduce that average for a given load factor — what it bounds is the tail, which matters for any workload with a latency budget rather than a throughput target. The cost is that insertion does more work, since it may displace several entries, and that plain insertion must compare probe distances on every step, which is one extra subtraction; Robin Hood swaps can in some variants be deferred to the key’s home slot, which keeps the insertion loop close to linear probing’s.

Most linear-probing designs avoid the cost differently, by nesting: a coalesced hash table descends to an array of fixed-size buckets whose last slot is a full pointer to a contiguous overflow area, and the sparse hash table in the same family allows a bucket to grow by one slot and moves slots into it so the overflow store stays small. Neither scheme restores a tail bound as tight as Robin Hood’s, but both keep the common case at a single indirection.

Choosing the table size

The probe sequence’s coverage depends on m, and the dependencies differ per family.

• Linear probing works for any m. Prime m is unnecessary; the modulo can be replaced by a mask when m is a power of two, which is the usual choice.
• Quadratic probing with the triangular sequence requires m to be a power of two for the sequence to be a permutation. With other m, the sequence may cycle through a proper subset and never find an empty slot even when one exists.
• Double hashing requires gcd(step, m) = 1. With m a power of two, forcing the step odd is sufficient and cheap.

The failure when the requirement is violated is not a wrong answer but an infinite loop: insertion keeps probing a subset of slots that are all occupied and never terminates. The standard defence is a probe counter that aborts after m steps and triggers a rehash, which converts a hang into a resize.

Load factor thresholds follow from the probe-count formulas. A table that must serve misses — an insert-heavy workload, or a cache with many lookups for absent keys — wants α below about 0.7 for linear probing and can go higher for double hashing. A table that only serves hits can run at α near 0.9 with linear probing and still average under six probes. The choice of threshold is therefore a statement about the read/write mix, not a universal constant, and the same reasoning appears in the bucket-occupancy trade in extendible hashing, where a bucket that splits on overflow settles at a comparable average fill.

Where open addressing loses to chaining

Chaining handles arbitrary load factors gracefully and deletion is trivial — unlink the node. Open addressing degrades sharply past a threshold and deletion is subtle. Chaining stores keys in separately allocated nodes, so a lookup follows a pointer that may miss cache; open addressing keeps everything in the table’s array, so a probe is a load from memory that is already being streamed.

The crossover depends on the size of the stored entries. For small entries — a 64-bit key and a 64-bit value — a table slot is 16 bytes and four slots share a 64-byte cache line, so linear probing’s contiguity is worth a great deal. For large entries, the table becomes a sparse array of big records and the cache advantage disappears; chaining, or an array of pointers into a separate entry store, becomes competitive.

There is also a correctness consideration that favours chaining in concurrent settings. Open addressing’s probe sequence makes a lookup read slots that another thread may be concurrently inserting into or shifting, and the backward-shift deletion above is not safe under concurrent readers without a scheme that keeps the shifted entries visible. Chaining’s unlink is a single pointer store, which is why concurrent hash maps tend to use buckets of short chains rather than open addressing.