Primary clustering — Aptitude Question
Primary clustering: Which collision-resolution scheme suffers from primary clustering, in which occupied slots pile… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 75 seconds
Question
Which collision-resolution scheme suffers from primary clustering, in which occupied slots pile up into long consecutive runs?
Options
- Double hashing
- Linear probing
- Quadratic probing
- Separate chaining
Show the answer and the worked solution
Correct answer: B. Linear probing
Worked solution
- Separate chaining stores colliding keys in lists outside the table, so no runs form inside it.
- Quadratic probing and double hashing spread successive probes with a growing or key-dependent step, so two keys rarely follow the same path.
- Linear probing always tries the next slot, so any run of occupied slots absorbs every key that hashes anywhere into it and grows longer still — that is primary clustering.
Answer: Linear probing.
The idea
Quadratic probing cures primary clustering but leaves secondary clustering, where keys sharing a home slot still share a probe path. Double hashing removes that too, at the cost of a second hash function.
Shortcut. Primary clustering needs a fixed step of 1 so that runs merge; quadratic probing and double hashing vary the step, and chaining keeps keys outside the table.
Common trap. "Quadratic probing" suffers secondary clustering, and the similar name makes it tempting, but it cures the primary kind.
All Data Structures & Algorithms questions · placement mock tests