Question

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

a)
77 mod 11 = 0
so, hash value of 77 is 0

109 mod 11 = 10
so, hash value of 109 is 10

69 mod 11 = 3
so, hash value of 69 is 3

99 mod 11 = 0
so, hash value of 99 is 0

16 mod 11 = 5
so, hash value of 16 is 5

100 mod 11 = 1
so, hash value of 100 is 1

60 mod 11 = 5
so, hash value of 60 is 5

b)
load factor = number of values / size of table
= 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