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

a) Find out hash values for each key (k)

b) Find out the load factor.

c) Construct Hash Table and use Linear Probing to resolve collision.

Answer 1

2)
a)
Hash value of 77 is 0
Hash value of 109 is 10
Hash value of 69 is 3
Hash value of 99 is 0
Hash value of 16 is 5
Hash value of 100 is 1
Hash value of 60 is 5

b)
load factor = 7/11

c)
[77, 109, 69, 99, 16, 100, 60]
Inserting 77
77 mod 11 = 0
77 is inserted at position 0

Number of cells visited during insertion is 1

Inserting 109
109 mod 11 = 10
109 is inserted at position 10

Number of cells visited during insertion is 1

Inserting 69
69 mod 11 = 3
69 is inserted at position 3

Number of cells visited during insertion is 1

Inserting 99
99 mod 11 = 0
There is already an item in 0
So, checking at index 1
99 is inserted at position 1

Number of cells visited during insertion is 2

Inserting 16
16 mod 11 = 5
16 is inserted at position 5

Number of cells visited during insertion is 1

Inserting 100
100 mod 11 = 1
There is already an item in 1
So, checking at index 2
100 is inserted at position 2

Number of cells visited during insertion is 2

Inserting 60
60 mod 11 = 5
There is already an item in 5
So, checking at index 6
60 is inserted at position 6

Number of cells visited during insertion is 2

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