Load thresholds for cuckoo hashing with double hashing

DOI10.4230/LIPICS.SWAT.2018.29MaRDI QIDQ5116493zbMATH OpenOpenAlexFDO

Authors Stefan Walzer, Michael Mitzenmacher, Konstantinos Panagiotou

Publication date 25 August 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8855/pdf/LIPIcs-SWAT-2018-29.pdf/

zbMATH Keywords

cuckoo hashingdouble hashinghypergraph orientabilityload thresholds

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Data structures (68P05) Hypergraphs (05C65) Arithmetic progressions (11B25)

Recommendations

• Sharp load thresholds for cuckoo hashing
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• The analysis of double hashing
• More analysis of double hashing
• Bipartite random graphs and Cuckoo hashing

Cites work

• A new approach to the orientation of random hypergraphs
• Balanced allocation and dictionaries with tightly packed constant size bins
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Cuckoo hashing
• Less hashing, same performance: Building a better Bloom filter
• More analysis of double hashing
• Some Open Questions Related to Cuckoo Hashing
• Space efficient hash tables with worst case constant access time
• The multiple-orientability thresholds for random hypergraphs

Cited in

(7)

• Dynamic space efficient hashing
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• More analysis of double hashing for balanced allocations
• Arithmetic progression hypergraphs: examining the second moment method
• Sharp load thresholds for cuckoo hashing
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• scientific article; zbMATH DE number 7525475 (Why is no real title available?)

This page was built for publication: Load thresholds for cuckoo hashing with double hashing

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