Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Let 
be the probability that the hash function 
.
A hash function which spreads keys evenly has the property that
for 
, 
In other words,
the hash values computed by the function 
are uniformly distributed .
Unfortunately,
in order to say something about the distribution of the hash values,
we need to know something about the distribution of the keys.
In the absence of any information to the contrary,
we assume that the keys are equiprobable.
Let 
be the set of keys that map to the value i.
I.e., 
.
If this is the case,
the requirement to spread the keys uniformly implies that 
.
An equal number of keys should map into each array position.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.