- 2071 Magh · 2 marks
Quadratic probing vs clustering
Short answer
Linear probing creates primary clustering as colliding keys fill consecutive slots, forming long runs. Quadratic probing uses offsets 1,4,9,… so probes jump farther apart, preventing keys from piling up next to each other and keys that hash to nearby slots do not share the same probe sequence.
How does quadratic probing help to reduce bad clustering problem associated with linear probing?
In linear probing, colliding keys fill consecutive slots (h, h+1, h+2, ...), so long filled runs form. Any key hashing into a run must walk to its end, and the run grows further. This is primary clustering.
Quadratic probing uses h(k, i) = (h(k) + i²) mod m, giving offsets 1, 4, 9, 16, ... The probe positions jump farther apart, so colliding keys do not pile up next to each other, and keys hashing to different but nearby slots do not share the same probe sequence.
Example (m = 10): keys 42, 52, 62 go to slots 2, 3, 4 with linear probing (a cluster), but to 2, 3, 6 with quadratic probing.
Quadratic probing still has mild secondary clustering, since keys with the same home slot follow the same sequence.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Linear and quadratic probing · Data Structure and Algorithm, chapter 8
- Linear, quadratic probing and double hashing · Data Structure and Algorithm, chapter 8
- Linear probing insertion into size-10 table · Data Structure and Algorithm, chapter 8
- Need of clustering; hierarchical vs partitioning; K-means · Data Mining, chapter 5
- Linear programming problem · Mathematics III, chapter 5