Question

Given input { 66, 28, 43, 29, 44, 69, 19 } and a hash function h(x) = x mod 10, show the resulting hash table:

1) Using Separate Chaining

2) Using Linear Probing

3) Using Quadratic Probing

Answer 1

1)
Inserting 66
66 is inserted at position 6
Inserting 28
28 is inserted at position 8
Inserting 43
43 is inserted at position 3
Inserting 29
29 is inserted at position 9
Inserting 44
44 is inserted at position 4
Inserting 69
69 is inserted at position 9
Inserting 19
19 is inserted at position 9
HashTable
-----------
0   -
1   -
2   -
3   -      43
4   -      44
5   -
6   -      66
7   -
8   -      28
9   -      29 -> 69 -> 19

2)
Inserting 66
66 mod 10 = 6
66 is inserted at position 6

Inserting 28
28 mod 10 = 8
28 is inserted at position 8

Inserting 43
43 mod 10 = 3
43 is inserted at position 3

Inserting 29
29 mod 10 = 9
29 is inserted at position 9

Inserting 44
44 mod 10 = 4
44 is inserted at position 4

Inserting 69
69 mod 10 = 9
There is already an item in 9
So, checking at index 0
69 is inserted at position 0

Inserting 19
19 mod 10 = 9
There is already an item in 9
So, checking at index 0
There is already an item in 0
So, checking at index 1
19 is inserted at position 1

HashTable
-----------
0   -      69
1   -      19
2   -
3   -      43
4   -      44
5   -
6   -      66
7   -
8   -      28
9   -      29

3)
Inserting 66
66 is inserted at position 6

Inserting 28
28 is inserted at position 8

Inserting 43
43 is inserted at position 3

Inserting 29
29 is inserted at position 9

Inserting 44
44 is inserted at position 4

Inserting 69
There is already an item in 9
So, checking at index 0
69 is inserted at position 0

Inserting 19
There is already an item in 9
So, checking at index 0
There is already an item in 0
So, checking at index 3
There is already an item in 3
So, checking at index 8
There is already an item in 8
So, checking at index 5
19 is inserted at position 5

HashTable
-----------
0   -      69
1   -     
2   -     
3   -      43
4   -      44
5   -      19
6   -      66
7   -     
8   -      28
9   -      29