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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• 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
• A Recurrence Related to Trees
• Efficient Ordering of Hash Tables
• Last-come-first-served hashing
• Ordered hash tables
• Reducing the retrieval time of scatter storage techniques
• Analysis of linear probing with buckets

Cited In (3)

• An approximate analysis of the performance of extendible hashing with elastic buckets
• The analysis of linear probing hashing with buckets
• Title not available (Why is that?)

Uses Software

• Digital Library of Mathematical Functions

Recommendations

• Title not available (Why is that?) 👍 👎
• On the analysis of linear probing hashing 👍 👎
• The analysis of linear probing hashing with buckets 👍 👎
• Fast and simple compact hashing via bucketing 👍 👎
• A unified approach to linear probing hashing 👍 👎
• Compact Hash Tables Using Bidirectional Linear Probing 👍 👎
• Hashing with Linear Probing under Nonuniform Probabilities 👍 👎
• Uniform hashing in constant time and linear space 👍 👎
• The analysis of linear probing hashing with buckets 👍 👎
• Fast and simple compact hashing via bucketing 👍 👎

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)