Quadratic Probing
You'll learn how quadratic probing improves upon linear probing by using quadratic increments to find empty slots, reducing the clustering problem.
The Core Idea
In the previous lesson, you saw that linear probing creates clusters—long runs of occupied slots that slow down future insertions and lookups. Quadratic probing solves this by checking slots at increasing distances rather than just moving one slot at a time.
Instead of probing positions hash + 1, hash + 2, hash + 3, quadratic probing uses:
hash + 1²(hash + 1)hash + 2²(hash + 4)hash + 3²(hash + 9)hash + 4²(hash + 16)- and so on...
Why This Helps
When multiple keys collide at the same index, quadratic probing "jumps" them to different areas of the table instead of packing them tightly together. This spreads out the occupied slots more evenly and breaks up primary clustering.
Visual Example
Imagine collisions at index 5:
- Linear probing: checks 5, 6, 7, 8, 9... (forms a tight cluster)
- Quadratic probing: checks 5, 6, 9, 14, 21... (spreads out)
The keys that collided at position 5 end up scattered across the table, so the next key that hashes to 6 won't have to wade through a long chain of occupied slots.
Important Note
Quadratic probing doesn't eliminate collisions—it just distributes them better. You still need a good hash function and must handle the case where no empty slot is found after many probes.
Key Takeaway: Quadratic probing uses squared increments (1, 4, 9, 16...) to jump over clusters, reducing the primary clustering problem that plagues linear probing.