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 Buckets

Authors: 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 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

    Share

    Consultation statistics

    This page has been seen 246 times.
    This article's PDF has been downloaded 641 times.