Alfredo Viola - Distributional analysis of Robin Hood linear probing hashing with buckets

dmtcs:3386 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3386
Distributional analysis of Robin Hood linear probing hashing with buckets

Authors: Alfredo Viola 1,2

  • 1 Universidad de la Rep├║blica [Montevideo]
  • 2 Laboratoire d'Informatique de Paris-Nord

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.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Distributional Analysis,Hashing,Linear Probing,Buckets,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Consultation statistics

This page has been seen 149 times.
This article's PDF has been downloaded 142 times.