Linear probing causes primary clustering (long runs of occupied slots). We need a probing sequence that skips more slots each time to reduce clustering.
Quadratic probing uses a quadratic function (i²) to determine probe sequence: h(k), h(k)+1², h(k)+2², h(k)+3², …
- Hash key to get initial index
- If collision, check index + 1²
- If still occupied, check index + 2²
- Continue: index + 3², index + 4², …
- Wrap around table as needed
- Reduces primary clustering compared to linear probing
- May not probe all slots (depends on table size)
- Works best when table size is prime number
- Load factor should be < 0.7 for good performance
- Built from: Hashing, Collision Resolution
- Builds into: Double Hashing
- Related: Linear Probing
- Contrasts with: Linear Probing (quadratic vs linear skip)
- May not probe all table slots (unlike linear probing)
- Table size should be prime for best coverage
- Secondary clustering: same initial hash = same probe sequence