A unified approach to linear probing hashing with buckets

DOI10.1007/S00453-015-0111-XzbMATH Open1350.68307arXiv1410.5967OpenAlexW1856022045MaRDI QIDQ308951FDOQ308951

Alfredo Viola, Svante Janson

Publication date: 6 September 2016

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (5)

• Lattice path combinatorics and linear probing
• An approximate analysis of the performance of extendible hashing with elastic buckets
• The analysis of linear probing hashing with buckets
• Distributional analysis of the parking problem and Robin Hood linear probing hashing with buckets
• Title not available (Why is that?)

Uses Software

• Digital Library of Mathematical Functions

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)