This question might look strange, so I will try to be clear.

Consider a hashing function $f : M \mapsto H$ which takes a message with arbitrary length $m \in M$ as input and returns a hash $h \in H$ of fixed length.

What I want to know is this. Consider to have $N$ different input messages and their hashes, well what I do is providing to $f$ a very very big number of messages, and I want to see how many times each possible hash will be returned (one hash can be returned twice of course or even more because of collision).

When i consider such operation I will get a probability distribution which describes that hashing function. What I want to know is:

  • What is the official name of this distribution?
  • Can I know such distributions for the most popular hashing functions?

And of course the most important thing: is it nonsense what I talked about so far, or it is something that does not even exist?

  • 1
    $\begingroup$ It is certainly not nonsense; it is essential to the analysis of the performance of hashing algorithms, and it is extensively studied. Try a search for the "balls-in-bins" problem. $\endgroup$ – MJD Oct 9 '12 at 14:06
  • $\begingroup$ @MJD: I am trying... thanks for you message :) $\endgroup$ – Andry Oct 9 '12 at 14:08

A good hash function should show a (nearly) uniform distribution of hash values, no matter what the distribution of the input values was, i.e. return hash $h \in H$ with probability $|H|^{-1}$.


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.