I have a hash function which maps elements from a set A to another set B. The size of the two sets are n and m respectively (with n >> m). The hash function is of the form -

$h: x' = x \; (mod \; m) \; | \; x \in A \;,\; x' \in B$

Thus, the elements in set B would be $\{0,1,2...(m-1)\}$. I want to compute the collision probability for any two elements in A ?

Any type of help would be highly appreciated.


The collision probability of Modulo hash function occurs for each couple of preimages located from a distance of $km$ for each integer $k<\frac{n}{m}$. But if $m$ doesn't divide $n$, there should be some side cases.

Let $k$ to be $\lfloor\frac{n}{m}\rfloor$

  • For two elements where one's index is located beyond $km$, the number of eventualities sums to $\binom{1}{k}(n \mod[m])$
  • If one element doesn't exceed this threshold or $m | n$, the occurences are just $\binom{2}{k}(m)$

To calculate the propability add up the two cases $P=P(Case_1)+P(Case_2)$ where $P(C_1\cap C_2)=0$ , the number to divide on is $\binom{1}{km}$ for the first case and $\binom{2}{km}$ in the other case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.