Fix linear probing’s clustering by jumping quadratically: try h, h+1, h+4, h+9, … (offsets i²). Keys that collide on the first slot then diverge fast, so primary clusters do not form. Here a key at home 3 (slots 3,4 full) skips to 7 — the offsets 1, 4, 9 spreading it out. With a prime table and load < ½, an empty slot is guaranteed.
THE TECHNIQUE slot = (h + i²) mod m
The demo shows the probe offsets are 1, 4, 9 (i²), landing the key at slot 7: live demo
HISTORY & CREDIT quadratic residues · table theory
“Quadratic probing always finds a slot.” — only if the table is at most half full and its size is prime; otherwise the i² sequence can miss empty slots. cited
the jump · offsets 0,1,4,9,16… spread colliders apart. no primary cluster · two keys sharing a home diverge after one step. the guarantee · prime m and load < ½ ⇒ a free slot exists (quadratic-residue argument).
Clustering broken by a parabola. data structure
RECOMMEND FOR I-13 the offsets, on the compiler
On i-13 (m=11, home 3, slots 3&4 full), the key lands at 7; offsets are i²:
$ i13 run hs_quadratic.i13
RUN OK · 121 step(s) · peak stack 11
found = 7 -- 3,4 full -> jump to 7
off1 = 4 -- (3+1) mod 11
off2 = 7 -- (3+4) mod 11
off3 = 1 -- (3+9) mod 11
quadratic_offsets = 1
Recommend as a NULL — resource (B40) + a pinned map (B39). Quadratic probing changes the probe schedule, not the stored map; it trades primary clustering for a load-factor constraint. A cost/robustness choice, not a same-function invariant. NULL — jump by squares.