# Understanding birthday celebration strike chances

I have 2 collections $M$ and also $H$. $M$ is an approximate string of size $k$ and also $H$ is an string of size $p$. Both are created from a charset of size $r$. And also $p<k$.

Hash function $f(m)=h$.

I recognize that $r^p$ hashes are feasible which $r^k-r^p$ crashes take place for the full set $M$.

Yet just how can I forecast the total probability for locating any kind of component of $M$ that appropriately maps to an offered component of $h$?

If the hash function is well created, the components of $M$ will certainly be just as dispersed throughout the hash values. So each component of $M$ will certainly have $r^{-p}$ opportunity of mapping to an offered component of $H$.

In this version, I'm not exactly sure just how you are counting crashes. Each component of $H$ will certainly receive $r^{(k-p)}$ of the strings in $M$. If your matter is to experience all the strings in $M$ and also matter one for each and every that hashes to a currently made use of value, you are proper.

Related questions