Applied Course | Mock GATE | Test 1 | Question: 57

Question

Insert the following keys in an array of size $17$ using the modulo division method. Use double hashing to resolve collisions. Take $h'(k) = (\text{key%}7)+1$ as the second hash function: $94, 37, 29, 40, 84, 88, 102, 63, 67, 120, 122$. What is the value present at location $7$ ____

Answer 1

There will be no collisions when you insert the elements $94, 37, 29, 40, 84.$ Those elements are placed at the locations $9, 3, 12, 6, 16.$ When you are trying to hash the element $88$, it will collision at the location $3$, so we will apply double hashing on it. It will place at the location $8$. The final hash table is after hashing all elements
$\begin{array}{|c|c|} \hline \text{value} & \text{Location} \\ \hline 102 & 0 \\ \hline 120 & 1 \\ \hline & 2 \\ \hline 37 & 3 \\ \hline 67 &  4 \\ \hline &  5 \\ \hline 40 &  6  \\ \hline 122 & 7 \\ \hline 88 & 8 \\ \hline 94 & 9 \\ \hline & 10 \\ \hline & 11 \\ \hline 29 & 12 \\ \hline 63 & 13 \\ \hline & 14 \\ \hline & 15 \\ \hline 84 & 16 \\ \hline \end{array}$

Comments

How will 88 hash to location 8 after we apply double hashing,shouldn't it be hashed to location 5 after applying double hashing because 88%7=4 isn't it??so,it shouldn't be 4+1=5??

---

@sanjay rao  DOUBLE HASHING = $(h_{1}(key) + h_{2}(key) .i)$%M

---

can someone explain how for 88 second hashing becomes 8

---

h1(k)= k mod 17

h2(k)= (k mod 7)+1

88 mod 17 results 3 where collision occurs and then we go with  2nd hash function

h2(k)=(88 mod  7) + 1 results 4 +1 =5 which we have to move 5 positions from 3 index which is its actual index

so 3+5 we go to 6 index position