0
$\begingroup$

When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number?

(This differs from Why is it best to use a prime number as a mod in a hashing function? because the prime number in question is the constant of the second hash function in a double hashing table, whereas the prime number in the other question is the mod of the hash table. In addition, it seems not that significant to avoid collisions because the second hash function in double hashing is used to determine the "jump size".)

$\endgroup$
  • $\begingroup$ The answers to that question already answer your question. See, e.g., this answer, which gives an example of a situation where a non-prime modulus to the hash function is bad, and this answer summarizes what is good about a prime modulus. Those answers aren't just talking about the number of buckets; they also apply to the modulus of the hash function. $\endgroup$ – D.W. Mar 30 '18 at 4:39
  • $\begingroup$ @D.W. I don't think this is a duplicate. The second hash function is used to determine the "jump size", for which it is not that significant to avoid collision. $\endgroup$ – xskxzr Mar 30 '18 at 5:44
  • $\begingroup$ Could you please explain where do you find the rule "the second hash function is defined as h2(x) = A - (x % A), where A is a prime number less than the capacity of the hash table"? $\endgroup$ – xskxzr Mar 30 '18 at 5:51
  • $\begingroup$ @xskxzr, cool. Want to make an edit asking about that aspect of things? I would agree that if the question focuses on that aspect (why does it need to be prime if collisions aren't that important) then it's no longer a dup. $\endgroup$ – D.W. Mar 30 '18 at 5:56

Your Answer

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.

Browse other questions tagged or ask your own question.