Question 3 : 30 points In some situations, the memory required to store linked lists in the hash table is not available. There is only enough space for the array itself. A closed hash table (also confusingly called open addressing) uses only a single array. We have two functions: a hash and a rehash. If two elements collide, we repeatedly use the rehash function until we find an empty slot. h(n,S) =n mod S hk(n,S) =(h(n, S) + k) mod S (8) (9) We'll insert the same values from the previous question into a closed hash table of size 4: (9, 13, 14, 3, 21). It is impossible to insert 5 elements into a closed hash table of size 4, so the last element (21) cannot be inserted. Given k = 1: ho(9,4) =1 ho(13, 4) =1 ho(14, 4) =2 ho(3, 4) =3 hi(13, 4) = 2 (Collision) hi(14, 4) = 3 (Collision) hi(3, 4) = 0 (Collision) (10) (11) (12) (13) 0 The closed hash table looks like this: Index Value 3 1 9 2 1 13 3 14 When checking to see if a value is in our hash table, in the worst case, we may need to search every slot in the table. If the size of the array is much larger than the number of elements, we can decrease the chance of a collision. Insert the following 10 numbers into a closed hash table with size S = 10: [45, 27, 100, 20,9, 24, 2, 13, 50, 12). Show the final hash table with all elements inserted. 3 points per element in the correct location