CODEWITHSUNDEEP
algorithmhash
Pippi
Pippi

Reputation: 2571

How does Cuckoo hashing insertion works?

According to documentation on how Cuckoo hashing insertion works, if value1 is to be inserted into table1 at position h1(key1) using hash function h1, and h1(key1) is already occupied because (key2, value2) was inserted such that h1(key2) = h1(key1), then Cuckoo hash algorithm computes h2(key2) and attempt to insert value2 at position h2(key2) in table2. This process repeats.

The lookup algorithm as described is : 

function lookup(x)
    return T1[h1(x)] = x ∨ T2[h2(x)] = x
end

However, when looking up the value of key2, value2 can be in h1(key2) or h2(key2). If h1(key1) = h1(key2), then h1(key1) can either be value1 (eviction occurred) or value2 (no eviction). How does the Cuckoo hash algorithm know which table to look for for value2?

Upvotes: 1

Views: 274

Answers (2)

MSalters
MSalters

Reputation: 179917

Only one way to find out: check both locations. Or in general, all locations where key2 could have gone.

Upvotes: 0

Pippi
Pippi

Reputation: 2571

It seems that the code is returning value at T2 first, and if that fails it returns value at T1. 

function lookup(x)
    return T1[h1(x)] = x ∨ T2[h2(x)] = x
end

Upvotes: 1

Related Questions