Question

Use double hashing and the following hash functions: hash(key) = (key % table size) and hash₂(key) = (16 - (key % 10)) + 1 to insert the following numbers into a dictionary's hash table: 1, 12, 14, 3, 5 and 17. The table size is 11. Show the table and where each value is inserted. No coding required for this problem.

Answer 1

Inserting 1
main hash value is 1
1 is inserted at position 1
-, 1, -, -, -, -, -, -, -, -, -

Inserting 12
main hash value is 1
There is already an item in 1
double hash value is 16
1 + 1*16 = 17
So, checking at index 17 % 11 = 6
12 is inserted at position 6
-, 1, -, -, -, -, 12, -, -, -, -

Inserting 14
main hash value is 3
14 is inserted at position 3
-, 1, -, 14, -, -, 12, -, -, -, -

Inserting 3
main hash value is 3
There is already an item in 3
double hash value is 16
3 + 1*16 = 19
So, checking at index 19 % 11 = 8
3 is inserted at position 8
-, 1, -, 14, -, -, 12, -, 3, -, -

Inserting 5
main hash value is 5
5 is inserted at position 5
-, 1, -, 14, -, 5, 12, -, 3, -, -

Inserting 17
main hash value is 6
There is already an item in 6
double hash value is 16
6 + 1*16 = 22
So, checking at index 22 % 11 = 0
17 is inserted at position 0
17, 1, -, 14, -, 5, 12, -, 3, -, -

HashTable
-----------
0   -      17
1   -      1
2   -     
3   -      14
4   -     
5   -      5
6   -      12
7   -     
8   -      3
9   -     
10      -