Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions

DOI10.1017/S0963548318000408MaRDI QIDQ5219328zbMATH OpenOpenAlexFDO

Authors

Publication date 11 March 2020

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

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

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms (68W40)

Recommendations

• Analysis of random probing hashing
• A new approach to analyzing Robin Hood hashing
• Distributional analysis of Robin Hood linear probing hashing with buckets
• On the analysis of linear probing hashing
• On probabilistic analysis of a coalesced hashing algorithm
• An Analysis of Random-Walk Cuckoo Hashing
• An analysis of random-walk cuckoo hashing
• On Worst-Case Robin Hood Hashing
• The analysis of linear probing hashing with buckets
• A Queueing Analysis of Hashing with Lazy Deletion

Cites work

• A new approach to analyzing Robin Hood hashing
• Efficient Ordering of Hash Tables
• scientific article; zbMATH DE number 4062573 (Why is no real title available?)
• scientific article; zbMATH DE number 53363 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Last-come-first-served hashing
• Ordered hash tables
• Reducing the retrieval time of scatter storage techniques
• The Analysis of Hashing Techniques That Exhibit k -ary Clustering
• The effect of deletions on different insertion disciplines for hash tables
• Uniform Hashing in Constant Time and Optimal Space
• Universal classes of hash functions

Cited in

(6)

• The effect of deletions on different insertion disciplines for hash tables
• Robin Hood hashing really has constant average search cost and variance in full tables
• On Worst-Case Robin Hood Hashing
• Concurrent Robin Hood hashing
• A new approach to analyzing Robin Hood hashing
• On deletions in open addressing hashing

This page was built for publication: Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions

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