Cuckoo Hashing

Question 1

Cuckoo Hashing

Answer 1

Another way to resolve collisions

Question 2

Idea

Answer 2

The cuckoo bird
o Shares a nest with other species o … then kicks the other species out
§ Same idea with cuckoo hashing

§ When we insert k1 we kick out what occupies the bucket, let’s say k2
§Then, k2 finds a new bucket

Question 3

Implementation

Answer 3

§ We have two hash tables T1 and T2

§ Collision strategy
o Each hash table has a hash function h1 and h2
o We prefer T1, but if we have to move we’ll go to T2
o If we are in T2 and have to move, we’ll go to T1

Question 4

Why two tables?

Answer 4

o Simple to visualize and implement
-Two hash functions h1 and h2 (one per table)

§ One table works just as well
-Using two hash functions h1 and h2

Question 5

Cuckoo Hashing running time

Answer 5

§ Cuckoo hashing guarantees
 o O(1) search, O(1) insert

§ Remember: other hashing strategies can’t guarantees this!

Question 6

Previous Collision Strategies

Answer 6

§Open addressing:
o Advantages: Simplicity and fixed memory usage
o Disadvantages:
-Deletions are problematic. Hence, chaining is more common when keys have to be deleted

§ Chaining:
o Advantages: Simplicity and fixed memory usage
-Simpler insertion and removal
o Disadvantages: Memory overhead is large if entries are small