Explicit and efficient hash families suffice for cuckoo hashing with a stash

DOI10.1007/s00453-013-9840-xzbMath1314.68106arXiv1204.4431OpenAlexW2149356828WikidataQ29013420 ScholiaQ29013420MaRDI QIDQ487008

Martin Aumüller, Philipp Woelfel, Martin Dietzfelbinger

Publication date: 19 January 2015

Published in: Algorithmica, Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.4431

zbMATH Keywords

random graphsdata structuresrandomized algorithmshash functionscuckoo hashinghash table

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)

Related Items

Efficient set intersection with simulation-based security, SSE and SSD: page-efficient searchable symmetric encryption, Bloom Filters in Adversarial Environments, Generalized cuckoo hashing with a stash, revisited, Hardness-preserving reductions via cuckoo hashing, Cuckoo hashing in cryptography: optimal parameters, robustness and applications, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Tight tradeoffs in searchable symmetric encryption, Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cuckoo hashing: Further analysis
• New hash functions and their use in authentication and set equality
• Universal classes of hash functions
• Space efficient hash tables with worst case constant access time
• Balanced allocation and dictionaries with tightly packed constant size bins
• Independence of Tabulation-Based Hash Classes
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
• Almost random graphs with simple hash functions
• Asymmetric balanced allocation with simple hash functions
• Applications of a Splitting Trick
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Cuckoo hashing
• The Power of Simple Tabulation Hashing
• More Robust Hashing: Cuckoo Hashing with a Stash
• More Robust Hashing: Cuckoo Hashing with a Stash