Load thresholds for cuckoo hashing with double hashing

DOI10.4230/LIPICS.SWAT.2018.29zbMATH Open1477.68084OpenAlexW2811247857MaRDI QIDQ5116493FDOQ5116493

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/

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

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)

Cites Work

• The Multiple-orientability Thresholds for Random Hypergraphs
• Cuckoo hashing
• Less hashing, same performance: Building a better Bloom filter
• Balanced allocation and dictionaries with tightly packed constant size bins
• A new approach to the orientation of random hypergraphs
• Space efficient hash tables with worst case constant access time
• More analysis of double hashing
• Some Open Questions Related to Cuckoo Hashing
• Convergence of Multivariate Belief Propagation, with Applications to Cuckoo Hashing and Load Balancing

Cited In (3)

• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Dynamic space efficient hashing
• Title not available (Why is that?)

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)