You have a hash table of length 11 tablesize 11 The hash k f

You have a hash table of length 11 (tablesize =11). The hash k function is h_1(key)+ key mod tablesize and using quadratic probing. After inserting the values , what is the final state of the hash table? Final condition: (if there isn\'t a number in one position, type-1. For example, if there\'s nothing in Hash Table [i], Hash Table[i] Hash Table

Solution

Insert values:
a) 22.
Hash key: 22% 11 = 0.
0th position is empty so insert 22 at 0th position.

b) 1
Hash key: 1 % 11 = 1.
1st position is empty so insert 1 at 1st position.

c) 13
Hash key: 13 % 11 = 2.
2nd position is empty so insert 13 at 2nd position.

d) 11
Hash key: 11 % 11 = 0.
0th position is not empty.
Quadratic probing needs to be done to find empty slot.
No of attempts required to find empty spot, i = 3
Position = hash key + i^2
= 0 + 3^2 = 9
9th position is empty so insert 11 at 9th position.

e) 24
Hash key : 24 % 11 = 2.
2nd position is not empty.
No of attempts required to find empty spot, i = 1
Position = hash key + i^2
= 2 + 1^2 = 3
Insert 24 at 3rd position

f) 33
Hash key: 33 % 11 = 0.
0th position is not empty.
No of attempts required to find empty spot, i = 4
Position = hash key + i^2
= 0 + 4^2 = 16
16 % 11 = 5
Insert 33 at 5th position

g) 18
Hash key: 18 % 11 = 7
Insert 18 at 7th position

h) 42
Hash key: 42 % 11 = 9
9th position is not empty.
No of attempts required to find empty spot, i = 1
Position = hash key + i^2
= 9 + 1^2 = 10
Insert 42 at 10th position.

i) 12
Hash key: 12 % 11 = 1
1st spot is not empty.
No of attempts required to find empty spot, i = 3
Position = hash key + i^2
= 1 + 3^2
= 10.
10 is not empty. Do quadratic probing for 10th spot.
= 10 + 5^2
= 35 % 11
= 2
2 is not empty. Do quadratic probing for 2nd spot.
= 2 + 2^2 = 6
Insert 12 at 6th position

0 -> 22
1 -> 1
2 -> 13
3 -> 24
4 ->
5 -> 33
6 ->
7 -> 18
8 ->
9 -> 11
10 -> 42