HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What are the advantages of cuckoo hashing over dynamic perfect hashing?

Submitted by: @import:stackexchange-cs··
0
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?

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.