Individual displacements for linear probing hashing with different insertion policies

DOI10.1145/1103963.1103964MaRDI QIDQ2944495zbMATH OpenOpenAlexWikidataFDO

Authors Svante Janson

Publication date 2 September 2015

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1103963.1103964

zbMATH Keywords

linear probing hashingRobin Hood hashing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Data structures (68P05)

Recommendations

• Exact distribution of individual displacements in linear probing hashing
• The maximum displacement for linear probing hashing
• Individual Displacements in Hashing with Coalesced Chains
• Asymptotic distribution for the cost of linear probing hashing
• Distributional analysis of Robin Hood linear probing hashing with buckets

Cited in

(12)

• Deviation results for sparse tables in hashing with linear probing
• A conditional Berry-Esseen inequality
• Parking functions for mappings
• scientific article; zbMATH DE number 7703264 (Why is no real title available?)
• scientific article; zbMATH DE number 7525476 (Why is no real title available?)
• Individual Displacements in Hashing with Coalesced Chains
• The maximum displacement for linear probing hashing
• A unified approach to linear probing hashing with buckets
• Asymptotic distribution for the cost of linear probing hashing
• Where should you park your car? The $\frac{1}{2}$ rule
• Parking distributions on trees
• Efficient data structures for sparse network representation

This page was built for publication: Individual displacements for linear probing hashing with different insertion policies

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