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. That is, . 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.