Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets

Alfredo Viola


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