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.
No takes yet. Share an insight, caveat, or question.
Svante Janson (2001) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: