Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
Preprint
Abstract
It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with stash size $s$ the probability of a rehash is $O(1/n^{s+1})$, and the evaluation time is $O(s)$. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (2010) (resp. $\Theta(\log n)$-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. As a byproduct, an algorithm for simulating uniform hashing is obtained. While it requires about twice as much space as the most space efficient solutions, it is attractive because of its simple and direct structure.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- More Robust Hashing: Cuckoo Hashing with a StashSIAM Journal on Computing, 2010
- A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess rDiscrete Mathematics & Theoretical Computer Science, 2010
- Uniform Hashing in Constant Time and Optimal SpaceSIAM Journal on Computing, 2008
- Balanced allocation and dictionaries with tightly packed constant size binsTheoretical Computer Science, 2007
- Space Efficient Hash Tables with Worst Case Constant Access TimeTheory of Computing Systems, 2004
- Cuckoo hashingJournal of Algorithms, 2004
- On Universal Classes of Extremely Random Constant-Time Hash FunctionsSIAM Journal on Computing, 2004
- Cuckoo hashing: Further analysisInformation Processing Letters, 2003
- A Reliable Randomized Algorithm for the Closest-Pair ProblemJournal of Algorithms, 1997
- Dependent Sets of Constant Weight Binary VectorsCombinatorics, Probability and Computing, 1997