UGC NET CSE | December 2010 | Part 2 | Question: 24

Question

Linear probing suffers from a problem known as

• A. Secondary clustering
• B. Primary clustering
• C. Both (A) and (B)
• D. None of these

Answer 1

Answer: B

Explanation - http://stackoverflow.com/a/27748735

Answer 2

Primary clustering means that if there is a cluster and the initial position of a new record would fall anywhere in the cluster the cluster size increases. Linear probing leads to this type of clustering. Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same. For example quadratic probing leads to this type of clustering.

Answer 3

linear probing suffers from both primary clustering and secondary clustering

many of places(like stackoverflow.. etc)  people are saying that linear probing suffers from primary clustering and quadratic probing suffers from secondary clustering.

Answer 4

B. Primary clustering ..

 

Linear probing is a term associated with hashing. Linear probing is a collision resolving technique in hashing. It suffers from a problem known as primary clustering.

Any chosen hash function should uniformly distribute the records across the given available address space but sometimes clusters appear.

If linear probing is used, it might spend a lot of time probing within the cluster instead of searching in the subsequent available space.

One more collision resolving technique is Quadratic probing. Again we might come across the same topic depending on the nature of question encountered in future....