Question

Suppose you have the following hash table, implemented using linear probing. The hash function we are using is the identity function, h(x) = x.

0	1	2	3	4	5	6	7	8
9	8		12	3	14	4	21

In which order could the elements have been added to the hash table? There are more than one correct answers, and you should give all of them. Assume that the hash table has never been resized, and no elements have been deleted yet.

1. 9, 14, 4, 18, 12, 3, 21
2. 12, 3, 14, 18, 4, 9, 21
3. 12, 14, 3, 9, 4, 18, 21
4. 9, 12, 14, 3, 4, 21, 18
5. 12, 9, 18, 3, 14, 21,4

Give explanation for your answer.

Answer 1

1) [9, 14, 4, 18, 12, 3, 21]
Inserting 9
9 is inserted at position 0

Inserting 14
14 is inserted at position 5

Inserting 4
4 is inserted at position 4

Inserting 18
There is already an item in 0
So, checking at index 1
18 is inserted at position 1

Inserting 12
12 is inserted at position 3

Inserting 3
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
3 is inserted at position 6

Inserting 21
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
There is already an item in 6
So, checking at index 7
21 is inserted at position 7

HashTable
-----------
0   -      9
1   -      18
2   -
3   -      12
4   -      4
5   -      14
6   -      3
7   -      21
8   -

2) [12, 3, 14, 18, 4, 9, 21]
Inserting 12
12 is inserted at position 3

Inserting 3
There is already an item in 3
So, checking at index 4
3 is inserted at position 4

Inserting 14
14 is inserted at position 5

Inserting 18
18 is inserted at position 0

Inserting 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
4 is inserted at position 6

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

Inserting 21
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
There is already an item in 6
So, checking at index 7
21 is inserted at position 7

HashTable
-----------
0   -      18
1   -      9
2   -
3   -      12
4   -      3
5   -      14
6   -      4
7   -      21
8   -

3) [12, 14, 3, 9, 4, 18, 21]
Inserting 12
12 is inserted at position 3

Inserting 14
14 is inserted at position 5

Inserting 3
There is already an item in 3
So, checking at index 4
3 is inserted at position 4

Inserting 9
9 is inserted at position 0

Inserting 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
4 is inserted at position 6

Inserting 18
There is already an item in 0
So, checking at index 1
18 is inserted at position 1

Inserting 21
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
There is already an item in 6
So, checking at index 7
21 is inserted at position 7

HashTable
-----------
0   -      9
1   -      18
2   -
3   -      12
4   -      3
5   -      14
6   -      4
7   -      21
8   -

4) [9, 12, 14, 3, 4, 21, 18]
Inserting 9
9 is inserted at position 0

Inserting 12
12 is inserted at position 3

Inserting 14
14 is inserted at position 5

Inserting 3
There is already an item in 3
So, checking at index 4
3 is inserted at position 4

Inserting 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
4 is inserted at position 6

Inserting 21
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
There is already an item in 6
So, checking at index 7
21 is inserted at position 7

Inserting 18
There is already an item in 0
So, checking at index 1
18 is inserted at position 1

HashTable
-----------
0   -      9
1   -      18
2   -
3   -      12
4   -      3
5   -      14
6   -      4
7   -      21
8   -

5) [12, 9, 18, 3, 14, 21, 4]
Inserting 12
12 is inserted at position 3

Inserting 9
9 is inserted at position 0

Inserting 18
There is already an item in 0
So, checking at index 1
18 is inserted at position 1

Inserting 3
There is already an item in 3
So, checking at index 4
3 is inserted at position 4

Inserting 14
14 is inserted at position 5

Inserting 21
There is already an item in 3
So, checking at index 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
21 is inserted at position 6

Inserting 4
There is already an item in 4
So, checking at index 5
There is already an item in 5
So, checking at index 6
There is already an item in 6
So, checking at index 7
4 is inserted at position 7

HashTable
-----------
0   -      9
1   -      18
2   -
3   -      12
4   -      3
5   -      14
6   -      21
7   -      4
8   -

Answer:
---------
iii)    12, 14, 3, 9, 4, 18, 21
iv)     9, 12, 14, 3, 4, 21, 18