Asymptotic distribution for the cost of linear probing hashing

Authors
Janson, S
Citation
S. Janson, Asymptotic distribution for the cost of linear probing hashing, RAND STR AL, 19(3-4), 2001, pp. 438-471
Citations number
30
Categorie Soggetti
Mathematics
Journal title
RANDOM STRUCTURES & ALGORITHMS
ISSN journal
10429832 → ACNP
Volume
19
Issue
3-4
Year of publication
2001
Pages
438 - 471
Database
ISI
SICI code
1042-9832(200110/12)19:3-4<438:ADFTCO>2.0.ZU;2-G
Abstract
We study moments and asymptotic distributions of the construction cost, mea sured as the total displacement. for hash tables using linear probing. Four different methods are employed for different ranges of the parameters: tog ether they yield a complete description. This extends earlier results by Fl ajolet, Poblete and Viola [On the analysis of linear probing hashing, Algor ithmica 22 (1998), 490-515]. The average cost of unsuccessful searches is c onsidered too. (C) 2001 John Wiley & Sons, Inc.