What will happen to the cuckoo hash table?

Computer Science Level 1

The following image shows an empty cuckoo filter . There are 6 buckets and 2 hash functions. The hash functions are shown. The following 5 numbers are inserted into the hash table.

[3, 7, 14, 15, 19]

Cukoo filter Cukoo filter

For reference, here is how the cuckoo filter works: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
Parameters of the Filter:
1. Two Hash Functions: h1 and h2
2. An array B with n buckets. The i-th bucket will be called B[i]

Input: L, a list of elements  to be inserted into the cuckoo filter.

Algorithm:
While L is not empty:
    Let x be the first item in the list L. Remove x from the list.
    If B[h1(x)] is empty:
        place x in B[h1(x)]
    Else, If B[h2(x) is empty]:
        place x in B[h2(x)]
    Else:
        Let y be the element in B[h2(x)].
        Prepend y to L
        place x in B[h2(x)]

Fill your answer in as a list of numbers. Leave a list slot empty if the corresponding bucket in the cuckoo table stays empty.

[19, 3, 15, 7, 14, ] [19, 3, 15, , 14, 7] [7, 3, 15, , 14, 19] The table will need to be resized [7, 3, 15, 19, 14, ]

Alex Chumbley by Alex Chumbley , 28, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Alex Chumbley
Aug 2, 2016

This hash table will put in the items in the following order:

3: hash1(3) = 2, so 3 is inserted into index 2

7: hash1(7) = 0, so 7 is inserted into index 0

14: hash1(14) = 1, so 14 is inserted into index 1

15: hash1(15) = 2. 2 is occupied. hash2(15) = 0, so 7 is removed from index 0 and 15 is placed in index 0

7 must be moved. hash2(7) = 2. 2 is occupied. 3 is removed from index 2 and 7 is placed in index 2

3 must be moved. hash2(3) = 0. 0 is occupied. We have already removed a number from index, so we have a loop.

Because we have encountered a loop, this hash table must be resized. This hash table has been poorly made because it only has 6 buckets and we wanted to insert 5 items. The probability that we would need to resize the hash table was very large. If we double the size of this hash table, this probability will be greatly reduced.

This can also be visualized by making a cuckoo graph from this cuckoo table. In the resulting bipartite graph, there will be two edges from the 3rd node on the left side to the 1st node on the right side. This results in infinitely many cycles in a connected segment of the graph (and two cycles of length 2). This means the table must be resized.

7 Helpful 0 Interesting 0 Brilliant 0 Confused

hash2(15) should be 3. The result is 7,19,3,15,14.

Yue Niu - 3 years, 1 month ago

Log in to reply

@Yue Niu mod 6(15*2) = mod 6(30) = 0

Michael Dey - 2 years, 11 months ago

Yue, (15*2) % 6 = 0

Narendra L - 1 year, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...