12
$\begingroup$

Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary space and access to families of hash functions for their operations.

I think that both of these data structures are beautiful and brilliant in their own right, but I'm not sure I see how and when one of these would be preferable over the other.

Are there specific contexts in which one of these data structures has a clear advantage over the other? Or are they mostly interchangeable?

Improve this question
$\endgroup$
5
  • $\begingroup$ I am not sure whether either of these techniques is actually used in practice. Usually these kinds of data structures that offer the best asymptotic bounds are mainly of research interest, since they usually have a large constant hidden in the $O$-notation. In practice you might prefer a simpler, easier to implement $O(\log n)$ technique with a really small constant over a more complicated $O(1)$ one with a really large constant. $\endgroup$
    – Tom van der Zanden
    Jan 22, 2015 at 7:27
  • $\begingroup$ @TomvanderZanden That's definitely true. I'm also interested in theoretical advantages of one approach over the other - are there any nice theoretical properties that each approach has to offer over the other? $\endgroup$
    – templatetypedef
    Jan 23, 2015 at 2:00
  • $\begingroup$ @templatetypedef, I encourage you to add that to the question, then. People shouldn't have to read the comments to understand your question -- comments are transitory and can disappear at any time. $\endgroup$
    – D.W. ♦
    Jan 23, 2015 at 5:36
  • $\begingroup$ Yes, these techniques are actually used in practice, usually in niche areas. $\endgroup$
    – Pseudonym
    Mar 24, 2015 at 6:20
  • 1
    $\begingroup$ One advantage of cuckoo hashing is that it is easy to understand and to implement. Also, imho, it is a lot easier to analyze than dynamic perfect hashing. $\endgroup$
    – A.Schulz
    Apr 23, 2015 at 9:32

4 Answers 4

Reset to default
3
$\begingroup$

Dynamic perfect hashing in the sense of Dietzfelbinger et al. only needs 2-independent hashing. While there are some results on simple hashing for cuckoo hash tables, such as twisted tabulation hashing and "Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash", the original dynamic perfect hashing is more robust in some sense.

Improve this answer
$\endgroup$
1
  • $\begingroup$ See the clarifying comment from OP: " I'm also interested in theoretical advantages of one approach over the other - are there any nice theoretical properties that each approach has to offer over the other?" $\endgroup$
    – jbapple
    Jan 23, 2015 at 5:06
3
$\begingroup$

In cuckoo hashing, lookups can be performed in parallel, while in Dietzfelbinger et al.'s original dynamic perfect hashing scheme, lookups require two chained memory accesses, in which the second access uses information retrieved from the first.

Improve this answer
$\endgroup$
1
$\begingroup$

It is relatively easy to increase the space efficiency of cuckoo hashing by allowing each slot to hold more than one item. For slots of size 4, the space efficiency is something like 95%. That is to say, items can be inserted until 95% of the space in the table is used to hold items, not just places where items might go.

On the other hand, the bounds in the Dietzfelbinger et al. paper on dynamic perfect hashing only prove that insert operations can proceed as long as the table is no more than 3% full.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You might want to combine your two answers together. :-) $\endgroup$
    – templatetypedef
    Jan 20, 2016 at 6:53
0
$\begingroup$

Cuckoo hashing uses $O(1)$ memory blocks at any one time and needs to free or reallocate memory rarely. Dynamic perfect hashing in the sense of Dietzfelbinger uses $O(n)$ memory blocks and will use more space in both internal and external fragmentation. There are ways to avoid this, but they add complexity to the algorithm.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.