DIMENSIONING A MULTIPLE HASHING SCHEME

Authors
BARBOUR AD PHATARFOD RM
Citation
Ad. Barbour et Rm. Phatarfod, DIMENSIONING A MULTIPLE HASHING SCHEME, Journal of Applied Probability, 34(2), 1997, pp. 477-486
Citations number
3
Categorie Soggetti
Statistic & Probability","Statistic & Probability
Journal title
Journal of Applied Probability → ACNP
ISSN journal
00219002
Volume
34
Issue
2
Year of publication
1997
Pages
477 - 486
Database
ISI
SICI code
0021-9002(1997)34:2<477:DAMHS>2.0.ZU;2-C
Abstract
The number of items of data which are irretrievable without additional effort after hashing can be greatly reduced if several hash tables ar e used simultaneously. Here we show that, in a multiple hashing scheme , this number has a distribution very close to Poisson. Thus choosing the number and sizes of the tables to minimize the expected number of irretrievable items is the right way to dimension a scheme.