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

dmtcs:519 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 2 - https://doi.org/10.46298/dmtcs.519
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with BucketsArticle

Authors: Alfredo Viola 1

  • 1 Pedeciba Informatica

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 alpha-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.


Volume: Vol. 12 no. 2
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: Distributional Analysis,Hashing,Linear Probing,Buckets,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 319 times.
This article's PDF has been downloaded 763 times.