Hashing with Linear Probing under Nonuniform Probabilities

DOI10.1017/S0269964800000577MaRDI QIDQ3415863zbMATH OpenFDO

Authors David Aldous

Publication date 19 January 2007

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Analysis of random probing hashing
• Asymptotic distribution for the cost of linear probing hashing
• Linear probing with 5-wise independence
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• The analysis of double hashing

Cites work

• Expected Length of the Longest Probe Sequence in Hash Code Searching
• scientific article; zbMATH DE number 3885030 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• Linear probing: The probable largest search time grows logarithmically with the number of records
• The analysis of double hashing
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform

Cited in

(14)

• Analysis of random probing hashing
• Multidimensional quantile hashing is very efficient for nonuniform distributions
• A Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0
• Parking with density
• A unified approach to linear probing hashing with buckets
• Dynamical model for the neural activity of singing \textit{serinus Canaria}
• Lossy Projective Hashing and Its Applications
• scientific article; zbMATH DE number 3902020 (Why is no real title available?)
• The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
• Nonoblivious hashing
• The analysis of linear probing hashing with buckets
• String hashing for linear probing
• Linear probing: The probable largest search time grows logarithmically with the number of records
• Two-way chaining for non-uniform distributions

This page was built for publication: Hashing with Linear Probing under Nonuniform Probabilities

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