patternMinor
What are the advantages of cuckoo hashing over dynamic perfect hashing?
Viewed 0 times
thewhatarecuckooadvantagesperfectdynamichashingover
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#37476, answer score: 4
Revisions (0)
No revisions yet.