Load Thresholds for Cuckoo Hashing with Double Hashing

DOI10.4230/LIPIcs.SWAT.2018.29zbMath1477.68084OpenAlexW2811247857MaRDI QIDQ5116493

Stefan Walzer, Michael Mitzenmacher, Konstantinos D. 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) Combinatorics in computer science (68R05) Data structures (68P05) Arithmetic progressions (11B25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Dynamic space efficient hashing ⋮ Unnamed Item

Cites Work

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

This page was built for publication: Load Thresholds for Cuckoo Hashing with Double Hashing