Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
Alfredo Viola
Abstract
This paper presents the first distributional analysis of both, a
parking problem and a linear probing hashing scheme with buckets of
size b. The exact distribution of the cost of successful
searches for a b α-full table is obtained, and
moments and asymptotic results are derived. With the use of the
Poisson transform distributional results are also obtained for tables
of size m and n elements. A key element in
the analysis is the use of a new family of numbers, called Tuba
Numbers, that satisfies a recurrence resembling that of the Bernoulli
numbers. These numbers may prove helpful in studying recurrences
involving truncated generating functions, as well as in other problems
related with buckets.
Full Text: PDF PostScript