Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

Details Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

2012-04-19

arxiv.org/abs/1204.4431v1

Computer Science

Data Structures and Algorithms

18 Pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35521