Suppose we have an initially empty hash table with 11 cells with hash function h
ID: 3717980 • Letter: S
Question
Suppose we have an initially empty hash table with 11 cells with hash function h (k)-k mod I, where I is the length of the hash table's array. Assuming linear probing with ? ?? + 2 insert the following sequence into the hash table if an insertion will result in 50% or more cell occupancy, rehash to 23 cells before attempting the insertion. 72, 88, 17, 121, 209, 111, 180, 295 Provide the final location of each key after all keys have been inserted. Ilf a cell is unoccupied, enter 'empty" without quotes. 0 2 3 4 8 10 12 13 14 15 16 17 18 19 20 21Explanation / Answer
Since we only have 8 keys and 23 cells, cell occupancy is clearly less than 50%
Now using the hash function on the given key values, we get the following output after modulus operation by 23 (since we have 23 cells)
Input to hash: [72, 88, 17, 121, 209, 111, 180, 295]
Output : [11, 13, 7, 20, 8, 13, 13, 13]
So putting these values in the hash table using linear probing for resolving collision, the hash map looks like this.
0 empty
1 empty
2 empty
3 empty
4 empty
5 empty
6 empty
7 17
8 209
9 empty
10 empty
11 72
12 empty
13 88
14 111
15 180
16 295
17 empty
18 empty
19 empty
20 121
21 empty
22 empty