---
title: "Quadratic probing vs clustering"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:quadratic-probing-clustering"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/quadratic-probing-clustering
site: BCT Engineering
---

# Quadratic probing vs clustering

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2071 Magh, 2 marks
- Video: [Hashing - Quadratic Probing explained with an example and the problem secondary clustering | ENGLISH](https://www.youtube.com/watch?v=0dGvg6Yzv4o) — abhikalitra - AKC CS Classes
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/quadratic-probing-clustering
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

How does quadratic probing help to reduce bad clustering problem associated with linear probing?

## 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.

## Answer

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is primary clustering in linear probing?
   A. Keys with identical hash values
   B. Table overflow
   C. Long runs of consecutive filled slots that keep growing
   D. Many empty slots in a row
   Answer: C. Colliding keys fill adjacent slots, and any key hashing into the run extends it. (Key point: Primary clustering)

2. Which offsets does quadratic probing use from the home slot?
   A. 1, 2, 3, 4, ...
   B. 2, 4, 6, 8, ...
   C. 1, 2, 4, 8, ...
   D. 1, 4, 9, 16, ...
   Answer: D. h(k, i) = (h(k) + i^2) mod m gives offsets i^2. (Key point: Quadratic offsets)

3. What mild problem remains with quadratic probing?
   A. Secondary clustering: keys with the same home slot follow the same sequence
   B. Primary clustering gets worse
   C. Keys can never be found again
   D. It needs a second hash function
   Answer: A. Same home slot means the same probe path, though different home slots no longer share paths. (Key point: Remaining problem)

## Related in Data Structure and Algorithm

- [Linear and quadratic probing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinear-quadratic-probing) — Data Structure and Algorithm, chapter 8
- [Linear, quadratic probing and double hashing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aprobing-double-hashing-resolve) — Data Structure and Algorithm, chapter 8
- [Linear probing insertion into size-10 table](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-linear-probing-62-37) — Data Structure and Algorithm, chapter 8

## Related in other subjects

- [Need of clustering; hierarchical vs partitioning; K-means](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Acluster-need-hier-vs-partition-kmeans) — Data Mining, chapter 5
- [Linear programming problem](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Alinear-programming-problem) — Mathematics III, chapter 5