A unified approach to linear probing hashing with buckets

DOI10.1007/S00453-015-0111-XMaRDI QIDQ308951zbMATHOpenAlexFDO

Authors Svante Janson, Alfredo Viola

Publication date 6 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5967

zbMATH Keywords

generating functionshashinganalytic combinatoricsbucketslinear probing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms (68W40) Searching and sorting (68P10)

Abstract: 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.

Recommendations

• The analysis of linear probing hashing with buckets
• The analysis of linear probing hashing with buckets
• A unified approach to linear probing hashing
• On the analysis of linear probing hashing
• Hashing with Linear Probing under Nonuniform Probabilities
• Distributional analysis of Robin Hood linear probing hashing with buckets
• Fast and simple compact hashing via bucketing
• Fast and simple compact hashing via bucketing
• Uniform hashing in constant time and linear space
• Compact Hash Tables Using Bidirectional Linear Probing

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2059980 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 194543 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A Recurrence Related to Trees
• A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0
• An Occupancy Discipline and Applications
• Analysis of Uniform Hashing
• Analysis of linear probing with buckets
• Analytic combinatorics
• Analytic combinatorics in several variables.
• Asymptotic distribution for the cost of linear probing hashing
• Big Buckets Are (Are Not) Better!
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Distributional analysis of the parking problem and Robin Hood linear probing hashing with buckets
• Efficient Ordering of Hash Tables
• Exact distribution of individual displacements in linear probing hashing
• Individual displacements for linear probing hashing with different insertion policies
• Last-come-first-served hashing
• Linear probing and graphs
• NIST handbook of mathematical functions
• On Ramanujan's \(Q\)-function
• On the analysis of linear probing hashing
• Ordered hash tables
• Phase transition for Parking blocks, Brownian excursion and coalescence
• Probability: a graduate course
• Quantum calculus
• Reducing the retrieval time of scatter storage techniques
• Singularity Analysis of Generating Functions
• The Diagonal Poisson Transform and its application to the analysis of a hashing scheme
• The analysis of linear probing hashing with buckets

Cited in

(6)

• A unified approach to linear probing hashing
• The analysis of linear probing hashing with buckets
• Distributional analysis of the parking problem and Robin Hood linear probing hashing with buckets
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• An approximate analysis of the performance of extendible hashing with elastic buckets
• Lattice path combinatorics and linear probing

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: A unified approach to linear probing hashing with buckets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q308951)