Hashing with Linear Probing under Nonuniform Probabilities
- 1 January 1988
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 2 (1) , 1-14
- https://doi.org/10.1017/s0269964800000577
Abstract
Probabilistic analyses of hashing algorithms usually assume that hash values are uniformly distributed over addresses. We study how one of the simplest schemes, hashing with linear probing, behaves in the nonuniform case. A simple measure μ of nonuniformity is the probability two keys hash to the same address, divided by this probability in the uniform case. It turns out that the effect of nonuniformity is to multiply mean search lengths by μ. For high loads, the longest search is multiplied by approximately μ also. Our theoretical results are asymptotics: simulations show good fits with predictions for mean search lengths, but bad fits for longest search lengths.Keywords
This publication has 6 references indexed in Scilit:
- On Probabilistic Analysis of a Coalesced Hashing AlgorithmThe Annals of Probability, 1987
- Linear probing: The probable largest search time grows logarithmically with the number of recordsJournal of Algorithms, 1987
- The expected length of the longest probe sequence for bucket searching when the distribution is not uniformJournal of Algorithms, 1985
- Expected Length of the Longest Probe Sequence in Hash Code SearchingJournal of the ACM, 1981
- The analysis of double hashingJournal of Computer and System Sciences, 1978
- Probability TheoryPublished by Springer Nature ,1978