Asymptotic distribution for the cost of linear probing hashing
Svante Janson · Random Structures and Algorithms · 2001
Abstract We study moments and asymptotic distributions of the construction cost, measured as the total displacement, for hash tables using linear probing. Four different methods are employed for different ranges of the parameters; together they yield a complete description. This extends earlier results by Flajolet, Poblete and Viola [On the analysis of linear probing hashing, Algorithmica 22 (1998), 490–515]. The average cost of unsuccessful searches is considered too. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 438–471, 2001