Question

Insertthe following numbres into a initially empty hash table of size 10. The functions h(x) = x % 10. Use linear probing when collision happens. Draw the hash tables and show the intermediate steps.

8,15,6,25,77,39

Answer 1

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

Number of cells visited during insertion is 1

Inserting 15
15 mod 10 = 5
15 is inserted at position 5

Number of cells visited during insertion is 1

Inserting 6
6 mod 10 = 6
6 is inserted at position 6

Number of cells visited during insertion is 1

Inserting 25
25 mod 10 = 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
25 is inserted at position 7

Number of cells visited during insertion is 3

Inserting 77
77 mod 10 = 7
There is already an item in 7
So, checking at index 8
There is already an item in 8
So, checking at index 9
77 is inserted at position 9

Number of cells visited during insertion is 3

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

Number of cells visited during insertion is 2

HashTable
-----------
0   -      39
1   -
2   -
3   -
4   -
5   -      15
6   -      6
7   -      25
8   -      8
9   -      77