Question

5. Below is an array with 15 positions, which is used as a hash table to keep some IDs. The key to each record is the 3-digit customer's ID. The hash function h gives the index of the slot in the array for the key k: h(k)=%15. The method of collision resolution is double hashing. Hence, if collision happens, we repeatedly compute (h(key) + iha(key)) mod 15, for i from 1 to 15, and he(key) = key%7 until an empty position is found (for adding an item to the hash table), or the key is matched (for retrieving an item from a hash table, given a key). Add the following keys to the hash table and show your calculations: 17, 42, 189, 24, 120, 78, 114, 146,282. The first four insertions are already made and calculations are shown. 1 0 24 2 3 4 5 6 7 8 17 10 11 9 189 12 13 14 42 h(17) = 17 mod 15 = 2, hence 17 goes to position 2 h(42) = 42 mod 15 = 12, hence 42 goes to position 12 h(189) = 189 mod 15 =9, hence 189 goes to position 9 h(24) = 24 mod 15 =9, hence 24 should go to position 9, but it is already taken. Applying double hashing: for i = 1: (h(24) +1.h2(24)) mod 15 = (9+3) mod 15 12, but this slot is taken as well, hence for i = 2: (h(24) +2.h2(24) mod 15 = (9+2.3) mod 15 = 0, this slot is not taken yet, use it.

Please Answer as soon as possible. Thank you so much.

Answer 1

Answer followed by explanation:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
24	120	17	78					146	189		114	42		282

Using a similar approach as used in inserting the first 4 elements we can insert the rest of the elements:

120: h(120) = 0. This is filled. Apply double hashing:

h(120) + 1.h2(120) = 0 + 1 = 1 which is empty hence 120 goes to position 1.

78: h(78) = 3 which is empty hence it goes to index 3.

114: h(114) = 9 . Filled:

h(114) + 1. h2(114) = 11 mod 15 = 11. Empty Hence 114 goes to 11.

146: h(146) = 11. Filled

h(146) + h2(146) = 11 + 6 mod 15 = 17 mod 15 = 2. Filled

h(146) + 2. h2(146) = 11 + 12 mod 15 = 23 mod 15 = 8. Empty Hence 146 goes to 8

282: h(282) = 12. Filled

h(282) + 1.h2(282) = 12 + 2 = 14 mod 15 = 14. Empty Hence 282 goes to index 14.

Finally, Hence the table looks like:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
24	120	17	78					146	189		114	42		282

You can comment below the answer, for any doubts, and I will be happy to help!

Please give a thumbs up if my answer could be of help!

All the best!