Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

DOI10.1007/978-3-540-95891-8_22zbMath1206.68101OpenAlexW1501716409MaRDI QIDQ3599076

Martin Dietzfelbinger, Ulf Schellbach

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-95891-8_22

zbMATH Keywords

data structureslower boundsrandomized algorithmscuckoo hashinguniversal hash classes

Mathematics Subject Classification ID

Data structures (68P05) Randomized algorithms (68W20)

Related Items (3)

An improved version of cuckoo hashing: average case analysis of construction cost and search operations ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• Cuckoo hashing: Further analysis
• Universal classes of hash functions
• Simulating BPP using a general weak random source
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Cuckoo hashing
• On the cell probe complexity of membership and perfect hashing
• More Robust Hashing: Cuckoo Hashing with a Stash

This page was built for publication: Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes