0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.