Linear and quadratic probing

Both are open-addressing methods: when the home slot h(k) = k mod m is occupied, other slots in the table are probed in a fixed order.

Linear probing

h(k, i) = (h(k) + i) mod m, for i = 0, 1, 2, ... The next free slot is used.

• Easy to implement and cache friendly.
• Causes primary clustering: filled slots join into long runs, so insertion and search get slower.

Quadratic probing

h(k, i) = (h(k) + c₁·i + c₂·i²) mod m, usually h(k) + i² (offsets 1, 4, 9, ...).

• Probes jump apart, which breaks up primary clustering.
• Keys with the same home slot follow the same probe path (secondary clustering).
• It may not reach every slot, so m and the constants must be chosen carefully. For example, with m prime and offsets i², a free slot is always found if the table is less than half full.

Example (m = 10, keys 42, 52, 62, 72)

Linear probing keeps the keys adjacent (2, 3, 4, 5), while quadratic probing spreads them out (2, 3, 6, 1).