# Why is the module of the second function in double hashing a prime number?

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".)

• 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.
– D.W.
Mar 30, 2018 at 4:39
• @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. Mar 30, 2018 at 5:44
• 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"? Mar 30, 2018 at 5:51
• @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.
– D.W.
Mar 30, 2018 at 5:56