Linear, quadratic probing and double hashing

When two keys hash to the same slot (a collision), open addressing searches for another free slot in the table using a probe sequence. Take table size m = 10, with keys 42, 52, 62, 72, which all have home slot 2 (h(k) = k mod 10).

Linear probing

h(k, i) = (h(k) + i) mod m. Slots tried: 2, 3, 4, 5, ...

• 42 goes to 2, 52 to 3, 62 to 4, 72 to 5.
• Simple, but forms long clusters (primary clustering).

Quadratic probing

h(k, i) = (h(k) + i²) mod m. Slots tried: 2, 3, 6, 11 mod 10 = 1, ...

• 42 goes to 2, 52 to 3, 62 to 6, 72 to 1.
• Avoids primary clustering, but keys with the same home slot still share one path (secondary clustering).

Double hashing

h(k, i) = (h1(k) + i·h2(k)) mod m, with h1(k) = k mod 10 and h2(k) = 7 − (k mod 7). The step size depends on the key.

• 42: slot 2.
• 52: h2 = 7 − 3 = 4; slot 2 is full, so the next slot is 2 + 4 = 6.
• 62: h2 = 7 − 6 = 1; slot 2 is full, so the next slot is 3.
• 72: h2 = 7 − 2 = 5; slot 2 is full, so the next slot is 7.

Double hashing gives the best spread because different keys with the same home slot get different steps. h2(k) must never be 0 and should be relatively prime to m (a prime table size guarantees this; m = 10 is used here only to keep the example simple).