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

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

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

(8)

• Dynamic space efficient hashing
• Sharp load thresholds for cuckoo hashing
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• Dense peelable random uniform hypergraphs
• More analysis of double hashing for balanced allocations
• Arithmetic progression hypergraphs: examining the second moment method
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures

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)