What is primary and secondary clustering in hash?
What is primary and secondary clustering in hash?
I am confused for the last few days in finding the difference between primary and secondary clustering in hash collision management topic in the textbook I am reading.
2 Answers
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.
x
x+1
x+2
x+3
x
x+1
x+4
x+9
x+16,
x+25
Were I to have ten more voting up right, I would do so.
– snr
Apr 29 '17 at 13:43
@snr Thanks, I'm glad you found it useful.
– Yogesh Umesh Vaity
Apr 29 '17 at 17:28
I was wondering if a Linear Congruential Probing scheme (say:
5*x+1 % size, applied repeatedly) would behave closer to a Linear or Quadratic probing scheme in terms of clustering. I am thinking Linear because x(n+1) only depends on x(n) thus clustering.– Matthieu M.
Oct 29 '17 at 13:50
5*x+1 % size
Thanks for contributing an answer to Stack Overflow!
But avoid …
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
But avoid …
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
I would like to add a clarification, (just in case the language of the answer created doubt). Secondary clustering happens in both Linear probing as well as Quadratic Probing, i.e. linear probing also suffers from secondary clustering.
– Roadblock
Mar 28 '16 at 17:08