Using closed hashing, with double hashing to resolve collisions, insert the foll

Question

Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of thirteen slots (the slots are numbered 0 through 12). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are using H1 and H2 to do the hashing. Function Rev(k) reverses the decimal digits of k, for example, Rev(37) = 73; Rev(7) = 7.

H1(k) =k mod 13.

H2(k) = (Rev(k+ 1) mod 11).

Keys: 2, 8, 31, 20, 19, 18, 53, 27.

The picture attached shows the solution. I don't understand what happens when 18 is inserted and H2 causes another collision.

9.16 Key: 2 8 31 20 19 18 53 27 H1 2 8 5 7 6 5 1 1 H2 3 9 1 1 2 3 1 5 Result of inserting 2 2 OK 8 8 OK 31 5 OK. 20 7 OK 19 6 OK. 18 5 Collision. So, try 5+3-8. Collision. Then 5+6 11. OK 53 1 OK. 27 1 Collision. So, try 1+5 6. Collision. Then 1+5+5 11. Collision. Then 1+5+5+5 13 3. OK Final table Position 0 1 2 3 4 5 6 7 8 9 10 11 12 53 2 27 18 31 19 20 8 Value

Explanation / Answer

Ans::

The insert algorithm for doubl-hashing is

a. Set the indx = H(K) & offset = H2(K).

b. If the tabl location index has already contains the 'key' then there is no need of inserting it. Done!

c. Else if the table_location index is empty then insert the 'key' there. Done!

d. Else collision. Set index = (index + offset) mod M.

e. If the index == H(K), table is full! --"Throw an exception, or enlarg the table" Else go to '2'.

If 2 keys 'collide' means then the next_positon should be the same for 'both'.

** So in the problem at '18' insertion the collision occurs therefore (index+offset) = 5+3=8 again there is collision and then "5+6 = 11" . // thank you //

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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