On the Performance of Balanced Hashing Functions When the Keys Are Not Equiprobable

Abstract

The cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. It is shown that the obvious strategy—trying to balance the sums of probabilities of the keys mapped to any given address—may be suboptimal; however, the difference from the exactly optimal distribution cannot be large.