Quadratic probing

Quadratic probing resolves hash-table collisions by stepping in quadratically increasing offsets from the initial bucket:

${\text{index}}_i=(h(k)+c_{1}i+c_2{i}^2)\mathrm{mod}M,i=0,1,2,\dots$

Typically $c_1=c_2=1$, giving the simple sequence $h(k),h(k)+2,h(k)+6,h(k)+12,\dots$ (step sizes $2,4,6,8,\dots$ — the differences between successive $i+i^2$ values).

The non-linear step spreads probes further apart, eliminating the primary clustering that plagues linear probing.

What it fixes vs. doesn’t

Fixed: primary clustering. Two keys with adjacent initial hashes ($h(k_1)=b$ and $h(k_2)=b+1$) follow probe sequences that immediately diverge — they no longer pile up into a contiguous run.

Not fixed: secondary clustering. Two keys with the same initial hash ($h(k_1)=h(k_2)=b$) share the entire probe sequence — they collide forever. They take longer to find than uniformly-random probe paths would predict.

For real-world hash distributions where $h$ is fairly uniform, secondary clustering is much milder than primary clustering. Quadratic probing performance lies between linear probing and ideal uniform hashing.

The $M$-must-be-prime catch

A subtle issue: with $c_1=c_2=1$, the probe sequence may not visit every bucket. In particular, only half the buckets are reachable when $M$ is even. Even with $M$ prime, the standard sequence visits only $\lceil M/2\rceil$ buckets — meaning the table can refuse insertion at $\alpha =0.5$ even though the table is half empty.

The standard guarantees:

• $M$ is prime, $0\le c_1,c_2\le 1$, $c_2\ne 0$, and $\alpha <0.5$ → the probe sequence finds an empty slot.

In practice, implementations either (a) use a power-of-two $M$ with the triangular numbers sequence $0,1,3,6,10,15,\dots$ (which provably visits every bucket when $M$ is a power of 2), or (b) use a prime $M$ and accept the $\alpha <0.5$ limitation.

Probe-count behaviour

No clean closed form for quadratic probing’s average probe count, but empirical measurements consistently land between linear and uniform-hashing levels:

$\alpha$	Linear (unsuccessful)	Quadratic (unsuccessful)	Uniform / double-hash (unsuccessful)
0.5	2.5	$\approx 2.0$	2.0
0.7	6.06	$\approx 3.0$	3.33
0.9	50.5	$\approx 7$	10

Quadratic probing’s main appeal: it captures most of the speedup over linear probing without the per-probe cost of computing a second hash function (as Double hashing does).

Cache cost

The downside compared to linear probing: probes touch non-adjacent memory cells. The first probe is one cache line; the second is somewhere $1$–$2$ cache lines away; later probes scatter further. So even though quadratic probing has a better probe count than linear, each probe is more likely to be a cache miss.

For modern CPUs where cache misses dominate, this often makes linear probing faster than quadratic in absolute terms — even at moderate-to-high load factors where quadratic’s probe count looks better on paper.

That’s why production hash tables almost universally use linear probing (with Robin Hood / hopscotch variants) rather than quadratic. Quadratic probing is more often a textbook intermediate step than a deployed choice.

Deletion

Same tombstone trick as linear: deleted slots get a tombstone marker so probe chains aren’t broken. Lookups skip tombstones, insertions can reuse them.

In context

Quadratic probing sits between Linear probing (cheapest probes, worst clustering) and Double hashing (best probe count, two hashes per lookup). All three are open-addressing schemes; the closed-address alternative is Separate chaining.

For comparison and full analysis, see Hash table.