Which clustering effect is linear probing especially susceptible to in…
2010
Which clustering effect is linear probing especially susceptible to in standard hash-table analysis?
Answer: B. Primary clustering — ConceptIn open addressing, clustering means that occupied table positions form patterns that increase later probe lengths. Linear probing checks consecutive…
- A.
Secondary clustering
- B.
Primary clustering
- C.
Both primary and secondary clustering
- D.
None of these
Attempted by 105 students.
Show answer & explanation
Correct answer: B
Concept
In open addressing, clustering means that occupied table positions form patterns that increase later probe lengths.
Linear probing checks consecutive positions, so a collision can enlarge a contiguous occupied run; that run then attracts more colliding keys.
Application
Positions 5, 6, and 7 are occupied, forming one contiguous run.
A new key whose probe reaches position 5 checks positions 5, 6, and 7 consecutively.
The key enters the next free position, extending the run and increasing later probe lengths.
This contiguous-run growth is called primary clustering.
Contrast
Secondary clustering classifies keys that share the same initial hash and follow the same probe sequence; it is distinct from the contiguous-run mechanism asked here.
Primary clustering is the growth of contiguous occupied runs under consecutive probing.
Both labels combine two distinct mechanisms, whereas the stem asks specifically about contiguous-run growth.
None of these is excluded because the contiguous-run mechanism has a standard clustering label among the choices.
Cross-check
The probe rule h(k), h(k)+1, h(k)+2, ... visits adjacent cells. Adjacency is exactly what creates and expands a primary cluster.
Therefore, linear probing suffers from primary clustering.