Given one table of size 7 and two hash functions h1(k) = k mod 7 and h2 (k) = |

Question

Given one table of size 7 and two hash functions h1(k) = k mod 7 and h2 (k) = | 33, 27, and 68 in order to an initially empty table using a 1-table implementation of Cuckoo hashing. Show how the table looks like after inserting all of these keys. What would happen if we now insert the key 40 to this table? Show what the final result will look like, or include an clear and detailed explanation of what is occurring with the table. k/7] mod 7, where .. is the floor function, insert the keys 19, 35,

Explanation / Answer

Cuckoo Hashing : Its a hasing techique where the worst case Lookup of a key value is O(1).

So we can hash our given input as follows:

first we create a table with the input and generate hashes for all the keys using the two fucntion as:

So now we start generating our tables as follows:

First number encountered is 19 so its h1(k) = 5 we place it in 5th position as:

Next number encountered is 35 so its h1 value is 0 which is free slot in table 1 so we fill this also as:

Now the next number encountered is 33 whose h1 value is 5 but in table1 we have already 19 filled in this slot

so its a collison, in Cuckoo hasing we move the already filled key to table2 and fill this new key in its place

so the 19 will go to its h2(key) value that is 2 and we fill 33 in table 1 5th location as:

Now the next number encountered is 27 its h1 value is 6 so we fill it in table1 without any collision as:

33

Now the next number encountered is 68 whose h1 value is 5 which is already filled in table 1 by 33 so its a collision so we move this 33 key to its table2 hash which is 4 and fill table 1 with 68 as :

Now we have one more key 40 whose h1 = 40 mod 7 = 5

and h2 will be = floor(40/7) mod 7 = 5

but as we can see in table 1 this palce is already occupied by 68 so we move 68 first to table2 using its h2 hash value 2 but in 2 we already having 19 so we recursively fill now till we get any vacant slot so we check now h1(19) = 5 so now 19 will come at 5th location in table1 but we have 40 there so we displace 40 now by its h2(40) = 5 so we place 40 in table2 5th location which is already vacant.

So our final hash table will be as follows:

19 35 33 27 68 h1(k) = k mod7 5 0 5 6 5 h2(k) = floor(k/7)mod7 2 0 4 3 2

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.