Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 bucketsConference paper

Authors: Alfredo Viola 1,2

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α -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 253 times.
This article's PDF has been downloaded 232 times.