THE DOUBLE HASHING — a dart

THE DOUBLE HASHING a second hash sets the stride

The best open-addressing probe: use a second hash for the step size — slot = h₁ + i·h₂. Different keys with the same home get different strides, so even secondary clustering (which quadratic probing still has) disappears. The probe sequence looks random per key. Here a key with h₁=3, h₂=4 first free-lands at slot 7 = (3 + 1·4) mod 11.

THE TECHNIQUE slot = (h₁ + i·h₂) mod m

The demo probes with stride h₂=4 and finds the first free slot at 7: live demo

HISTORY & CREDIT de Balbine; Guibas & Szemerédi

“Any second hash works.” — h₂ must be nonzero and coprime to m (else the probe sequence cannot reach every slot); a prime m makes any h₂ < m coprime. cited

the stride · h₂(k) gives each key its own step.
no secondary cluster · same-home keys walk different sequences.
1976-78 · analyzed by Guibas & Szemerédi; behaves like uniform hashing.

The gold standard of probing. data structure

RECOMMEND FOR I-13 the stride, on the compiler

On i-13 (h₁=3, h₂=4, m=11, slots 0,3,6 full), the first free slot is 7:

$ i13 run hs_double.i13 RUN OK · 75 step(s) · peak stack 11 first = 7 step_uses_h2 = 7 -- (3 + 1*4) mod 11 probed = 1

Recommend as a NULL — resource (B40) + a pinned map (B39). Double hashing improves the probe distribution; the stored map is unchanged. Coprimality of h₂ and m is a correctness condition, not a new invariant. NULL — a second hash for the stride.