Question

1. (10 pts) Draw the result of hashing 11, 22, 3, and 43 into a table using the following hash function, using separate chaining:

h(x) = x % 4

              

0
1
2
3

2. (10 pts) Draw the result of hashing 11, 22, 3, and 43 into a table using the following hash function, using open addressing with linear probing:

h(x) = x % 4

0
1
2
3

Answer 1

1)
Inserting 11
11 is inserted at position 3

Inserting 22
22 is inserted at position 2

Inserting 3
3 is inserted at position 3

Inserting 43
43 is inserted at position 3

HashTable
-----------
0   -
1   -
2   -      22
3   -      11 -> 3 -> 43

2)
[11, 22, 3, 43]
Inserting 11
11 mod 4 = 3
11 is inserted at position 3

Number of cells visited during insertion is 1 

Inserting 22
22 mod 4 = 2
22 is inserted at position 2

Number of cells visited during insertion is 1 

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

Number of cells visited during insertion is 2 

Inserting 43
43 mod 4 = 3
There is already an item in 3
So, checking at index 0
There is already an item in 0
So, checking at index 1
43 is inserted at position 1

Number of cells visited during insertion is 3 

HashTable
-----------
0   -      3
1   -      43
2   -      22
3   -      11