Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
add comment

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
add comment

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.