1
$\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".)

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 5:56

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.