The Maximum Displacement for Linear Probing Hashing

DOI10.1017/S0963548312000582zbMath1262.68192OpenAlexW2109732586MaRDI QIDQ4921572

Niclas Petersson

Publication date: 13 May 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548312000582

zbMATH Keywords

linear probing hashingfirst-come-first-servemaximum displacementfirst-comeinsertion policy

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Searching and sorting (68P10) Combinatorial probability (60C05)

Related Items (1)

The Integral of the Supremum Process of Brownian Motion

Cites Work

• Unnamed Item
• Unnamed Item
• On the analysis of linear probing hashing
• On the distribution of Brownian areas
• A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0
• Individual displacements for linear probing hashing with different insertion policies
• Exact distribution of individual displacements in linear probing hashing
• Phase transition for Parking blocks, Brownian excursion and coalescence
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Last-come-first-served hashing
• On Worst-Case Robin Hood Hashing
• The Integral of the Supremum Process of Brownian Motion

This page was built for publication: The Maximum Displacement for Linear Probing Hashing