Question

3. Assume that you have a seven-slot hash table (the slots are numbered 0 through 6). Show the final hash table that would result if you used the following approach to put 7, 13, 10,6 into the hash (4 points each) the hash function h(k)-k mod 7 and linear probing function the hash function h(k)-k mod 7 and quadratic probing (a) (b)

Answer 1

a. Hash function using linear probing will put 7,13,10,6 into hash table as follows:-

h(7) = 7 mod 7 = 0, so 7 will be put into index 0.

h(13) = 13 mod 7 = 6, so 13 will be put into index 6.

h(10) = 10 mod 7 = 3. so 10 will be put into index 3

h(6) = 6 mod 7 = 6. But since index 6 is already occupied by 13, so in linear probing next index for inserting a key is search by moving one index ahead. So after index 6, next index is 0 which is also occupied. So next index 1 is available. So 6 will be inserted at index 7.

Below table shows the entry of these elements into the hash table.

0	1	2	3	4	5	6
7	6		10			13

b. Hash function using quadratic probing will put 7,13,10,6 into hash table as follows:-

h(7) = 7 mod 7 = 0, so 7 will be put into index 0.

h(13) = 13 mod 7 = 6, so 13 will be put into index 6.

h(10) = 10 mod 7 = 3. so 10 will be put into index 3

h(6) = 6 mod 7 = 6. But since index 6 is already occupied by 13, so in quadratic probing, next index to search is i² index ahead where i is number of collision occurred. For the first time i=1, so 1 index ahead to 6 is index 0, which is also occupied. Now i=2, so the next increment of index will be i² = 2²=4. Since 1+4=5, so index 5 will be searched next. Since index 5 is vacant, so 6 will be put at index 5.

Below table shows the entry of these elements into the hash table.

0	1	2	3	4	5	6
7			10		6	13

Please comment for any clarification.