Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have two sets $M$ and $H$. $M$ is an arbitrary string of length $k$ and $H$ is an string of length $p$. Both are constructed from a charset of length $r$. And $p<k$.

Hash function $f(m)=h$.

I understand that $r^p$ hashes are possible and that $r^k-r^p$ collisions occur for the complete set $M$.

But how can I predict the overall probability for finding any element of $M$ that correctly maps to a given element of $h$?

share|cite|improve this question

If the hash function is well constructed, the elements of $M$ will be equally distributed across the hash values. So each element of $M$ will have $r^{-p}$ chance of mapping to a given element of $H$.

In this model, I'm not sure how you are counting collisions. Each element of $H$ will receive $r^{(k-p)}$ of the strings in $M$. If your count is to go through all the strings in $M$ and count one for each that hashes to an already used value, you are correct.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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