# Distributional analysis of Robin Hood linear probing hashing with buckets

Abstract : This paper presents the first distributional analysis of 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 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [25 references]

https://hal.inria.fr/hal-01184221
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 13, 2015 - 1:35:02 PM
Last modification on : Wednesday, January 19, 2022 - 3:37:22 AM
Long-term archiving on: : Saturday, November 14, 2015 - 10:24:21 AM

### File

Publisher files allowed on an open archive

### Citation

Alfredo Viola. Distributional analysis of Robin Hood linear probing hashing with buckets. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.297-306, ⟨10.46298/dmtcs.3386⟩. ⟨hal-01184221⟩

Record views