Double Hashing and Quadratic Probing Without Primary Clustering

Linear probing fails because its probe sequences are parallel: every key that hashes into a run walks the same direction through the same cells. The fix is to make the sequences diverge, either by giving each key its own stride or by making successive offsets grow. Both eliminate primary clustering, and each introduces a different constraint on the table size and a different arithmetic bill.

Quadratic probing and the triangular-number trick

Quadratic probing uses offsets that grow quadratically: slot (h(k) + c₁·i + c₂·i²) mod m. The simplest and most common form drops the linear term and uses (h(k) + i²) mod m.

The consequence is that two keys with the same home slot still follow the same sequence of offsets, so they still collide at every step. What changes is that a key hashing to a nearby slot does not join the same run. The clustering that remains is called secondary clustering, and it is much weaker than primary clustering: keys collide only if their home slots are identical, not merely adjacent.

Quadratic probing also has a subtlety that trips implementations. The sequence i² mod m is not a permutation of the slots for arbitrary m. With m a power of two, i² mod 2^b takes only 2^(b-1) distinct values, because i and m - i have the same square, so half the table is unreachable from any home slot. A table that appears half empty can fail to accept an insertion.

Two standard repairs exist. The first uses a prime modulus and relies on the fact that the first m/2 squares are distinct modulo an odd prime, which guarantees a free slot while the table is less than half full. The second uses triangular numbers instead of squares: offsets i(i+1)/2. The recurrence T(i+1) = T(i) + i + 1 means the probe can be advanced by incrementing a step counter:

size_t probe_quadratic(struct table *t, unsigned long h, const char *key)
{
    size_t m = t->mask + 1, i = h & t->mask, step = 1;
    for (size_t n = 0; n < m; n++) {
        if (t->slot[i].state == EMPTY) return i;      /* free slot for insert */
        if (t->slot[i].state == OCCUPIED && key_eq(&t->slot[i], key)) return i;
        i = (i + step) & t->mask;                     /* T(i+1) - T(i) = i+1 */
        step++;
    }
    return SIZE_MAX;                                  /* table full */
}

For a power-of-two table, the triangular sequence visits every slot exactly once. The proof is that the partial sums T(i) mod 2^b are distinct for 0 ≤ i < 2^b, which follows by induction on the bits of i and is the reason the sequence is used in place of plain squares. The cost is one addition and one increment per probe, with no multiplication in the loop.

Deletion still needs tombstones, because a quadratic sequence has no local structure that permits backward shifting. The cluster is not contiguous, so a hole cannot be repaired by pulling neighbours back; the only correct removal is a marker that says “continue”.

Double hashing as the closest approximation to uniform

Double hashing derives both the home slot and the stride from the key: (h₁(k) + i·h₂(k)) mod m. Two keys that share a home slot but have different strides diverge immediately, so secondary clustering disappears as well. The result is that double hashing’s expected probe count matches the uniform-hashing bound closely, and it is the best of the practical schemes by that measure.

The constraint is arithmetic. The sequence visits every slot exactly when h₂(k) is coprime with m. Two standard configurations satisfy it:

• m prime, with h₂(k) constrained to [1, m-1]. Any nonzero stride is coprime with a prime, so the constraint reduces to avoiding zero.
• m a power of two, with h₂(k) forced odd. Every odd number is coprime with a power of two.

The second is much cheaper, since both the modulus and the coprimality check reduce to bit operations. The price is that the table size must be a power of two and the hash must supply an odd stride, which usually means deriving the stride from a different part of the hash than the index.

A cheap implementation computes h₂ by taking the high bits of a 64-bit hash, forcing the low bit, and optionally scaling to keep the stride small. Keeping the stride small matters for locality: a stride near m/2 sends every probe to the opposite half of the table, producing one cache miss per probe with no chance of sharing a line.

The probe count follows the uniform formula, 1/(1-α) for a miss and (1/α)·ln(1/(1-α)) for a hit, with the caveat that the independence assumption holds only if h₁ and h₂ are independent. Deriving both from the same hash word without mixing produces correlated strides, which reintroduces the clustering the scheme was meant to remove.

Comparing the three sequences on the same table

The differences are easiest to see side by side at a fixed load factor.

Sequence	Miss probes at α = 0.5	Miss at α = 0.9	Per-probe cost	Deletion
Linear	2.5	50.5	one add, contiguous access	backward shift possible
Quadratic (triangular)	between linear and double	between linear and double	one add, non-contiguous	tombstone required
Double	2.0	10.0	add plus stride multiply, non-contiguous	tombstone required

The quadratic row is the awkward one to quantify. Quadratic probing removes primary clustering, because keys with different home slots no longer share a run, but it keeps secondary clustering, because keys with the same home slot still follow the same offsets. Its expected probe count therefore sits between the linear and double-hashing formulas, closer to double hashing when the load factor is moderate and diverging as the load rises. No closed form as simple as the other two exists, which is one reason implementations choose it for its cheap arithmetic rather than for its cost curve.

What separates the schemes most sharply is the cost per probe. Linear probing’s probes are contiguous, so a run of k probes touches roughly k/8 cache lines. Double hashing’s probes are scattered, so each probe is its own line. At α = 0.9, double hashing needs about 10 probes and therefore about 10 cache misses, while linear probing needs an expected 50.5 probes but a run that stays inside the array walks contiguous memory, so the theoretically worse scheme can be the faster one on hardware. That is why the theoretical ranking and the practical ranking disagree.

The sequence should therefore be chosen against the load factor the table will actually run at. A table held at α ≤ 0.5 can afford linear probing’s clustering and benefits from its locality. A table that must run at α = 0.85 needs a miss cost near 6.7 probes, which double hashing’s bound provides, whereas linear probing’s formula gives about 22 at the same load.

Tombstones, again, and the fill counter

Both schemes require tombstones, and both therefore require the second counter that tracks occupied plus deleted slots. The counter must be maintained on every insert and every delete, and the resize decision must consult it rather than the live key count. A table with ten live keys and a thousand tombstones behaves like a table at α = 1 for every miss, and a load factor computed from live keys reports 0.01.

The usual policy is to rebuild when (live + deleted)/m crosses the same threshold that triggers growth, or when deleted exceeds a fraction of live. Rebuilding reinserts only the live keys, which both compacts the table and clears the markers, at Θ(live) cost. Implementations that shrink also use this path, since a table that once held a million keys and now holds ten wastes the array.

There is a correctness trap in the tombstone logic that is worth stating precisely. During insertion, the first deleted slot encountered is a candidate, but the search must continue to the end of the probe sequence to check whether the key is already present further along. Inserting into the tombstone immediately would leave a duplicate key in the table, and a later lookup would find whichever copy its probe reached first. The first_free pattern shown in open addressing handles this, and every correct implementation carries some equivalent of it.

None of these schemes bounds the worst case. An adversary who can choose keys that collide under both hash functions still produces long sequences, so the defences in hash flooding apply equally here. Bounding the worst case directly, by capping probe length and rebuilding, is a different strategy, taken up in Robin Hood hashing.