Take the 2-minute tour ×

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?

share|improve this question
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. –  MJD Oct 9 '12 at 14:06
@MJD: I am trying... thanks for you message :) –  Andry Oct 9 '12 at 14:08

1 Answer 1

up vote 2 down vote accepted

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}$.

share|improve this answer

Your Answer


