The expected length of the longest probe sequence for bucket searching when the distribution is not uniform

DOI10.1016/0196-6774(85)90015-XzbMath0571.68047OpenAlexW1987576061MaRDI QIDQ3687729

Luc P. Devroye

Publication date: 1985

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(85)90015-x

zbMATH Keywords

separate chainingcollision resolutionhashing file

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

Analytical depoissonization and its applications, Search performance of double-linked coalesced hashing can not exceed bucketing, Parking with density, The Maximum Displacement for Linear Probing Hashing, Cuckoo hashing: Further analysis, Hashing with Linear Probing under Nonuniform Probabilities, Two-way chaining for non-uniform distributions, Laws of large numbers and tail inequalities for random tries and PATRICIA trees