Question

2. Given the following keys: 77, 109, 69, 99, 16, 100, 60 Also given h(k) = k mod m Given size of the Hash Table (m) = 11

For the problem given above, illustrate Double Hashing to resolve the collision. The second has function is: h2(k) = 10 – (k mod 10)

Answer 1

Inserting 77
main hash value is 0
77 is inserted at position 0
77, -, -, -, -, -, -, -, -, -, -

Inserting 109
main hash value is 10
109 is inserted at position 10
77, -, -, -, -, -, -, -, -, -, 109

Inserting 69
main hash value is 3
69 is inserted at position 3
77, -, -, 69, -, -, -, -, -, -, 109

Inserting 99
main hash value is 0
There is already an item in 0
double hash value is 1
0 + 1*1 = 1
So, checking at index 1 % 11 = 1
99 is inserted at position 1
77, 99, -, 69, -, -, -, -, -, -, 109

Inserting 16
main hash value is 5
16 is inserted at position 5
77, 99, -, 69, -, 16, -, -, -, -, 109

Inserting 100
main hash value is 1
There is already an item in 1
double hash value is 10
1 + 1*10 = 11
So, checking at index 11 % 11 = 0
There is already an item in 0
double hash value is 10
1 + 2*10 = 21
So, checking at index 21 % 11 = 10
There is already an item in 10
double hash value is 10
1 + 3*10 = 31
So, checking at index 31 % 11 = 9
100 is inserted at position 9
77, 99, -, 69, -, 16, -, -, -, 100, 109

Inserting 60
main hash value is 5
There is already an item in 5
double hash value is 10
5 + 1*10 = 15
So, checking at index 15 % 11 = 4
60 is inserted at position 4
77, 99, -, 69, 60, 16, -, -, -, 100, 109

HashTable
-----------
0    -    77
1    -    99
2    -   
3    -    69
4    -    60
5    -    16
6    -   
7    -   
8    -   
9    -    100
10    -    109