A Unified Approach to Linear Probing Hashing with Buckets
2016 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 75, no 4, 724-781 p.Article in journal, Meeting abstract (Refereed) PublishedText
We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on q-calculus) to directly derive the generating functions to analyze.
Place, publisher, year, edition, pages
2016. Vol. 75, no 4, 724-781 p.
Hashing, Linear probing, Buckets, Generating functions, Analytic combinatorics
Probability Theory and Statistics Mathematical Analysis
IdentifiersURN: urn:nbn:se:uu:diva-299020DOI: 10.1007/s00453-015-0111-xISI: 000377359000006OAI: oai:DiVA.org:uu-299020DiVA: diva2:948871
Meeting of Algorithmica on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms, 2014, paris, FRANCE