Open addressing with the simplest probe: if the slot is taken, try h+1, h+2, … until an empty one. No pointers, great cache behavior — but collisions form primary clusters that lengthen every future probe near them. Here three keys hashing to slot 5 land at probe distances 0, 1, 2 — the cluster growing one slot at a time.
THE TECHNIQUE slot = (h + i) mod m
The demo inserts three colliding keys and shows the probe distances grow 0,1,2: live demo
HISTORY & CREDIT Amble & Knuth; analysis 1963
“Linear probing is obsolete.” — its cache-friendliness makes it the fastest in practice at low load; Knuth’s 1963 analysis of it launched the analysis of algorithms. cited
the probe · h, h+1, h+2, … until empty. the cluster · runs of full slots merge and grow — primary clustering. 1963 · Donald Knuth’s analysis of linear probing is the founding paper of algorithm analysis.
Fast until it clusters. data structure
RECOMMEND FOR I-13 the cluster, on the compiler
On i-13, three keys at slot 5 probe 0, 1, then 2 (wrapping):
$ i13 run hs_linear.i13
RUN OK · 143 step(s) · peak stack 7
p1 = 0 -- slot 5 empty
p2 = 1 -- 5 full, land at 6
p3 = 2 -- 5,6 full, wrap to 0
clustering = 1
Recommend as a NULL — resource (B40) + a pinned map (B39). The probe distance is amortized cost; the stored key→value map is identical to chaining’s. Clustering is a performance property, not a same-function invariant. NULL — try the next slot.