Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Spreading Keys Evenly

Let tex2html_wrap_inline57649 be the probability that the hash function tex2html_wrap_inline61373. A hash function which spreads keys evenly has the property that for tex2html_wrap_inline61375, tex2html_wrap_inline61377 In other words, the hash values computed by the function tex2html_wrap_inline58419 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 tex2html_wrap_inline61381 be the set of keys that map to the value i. That is, tex2html_wrap_inline61385. If this is the case, the requirement to spread the keys uniformly implies that tex2html_wrap_inline61387. An equal number of keys should map into each array position.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.