Imagine a hash table implementation where collisions are resolved by chaining but all the data stays within the slots of the original table. All entries not containing key-value pairs are marked with a Boolean flag and linked together into a free list.
(i) Give clear explanations on how to implement the set(key, value) method in expected constant time, highlighting notable points and using high-level pseudocode where appropriate. Make use of doubly-linked lists if necessary. (
ii) Assume the hash table has 5 slots, is initially empty and uses the hash function h(x) = x mod 5. Draw five diagrams of the hash table representing the initially empty state and then the table after the insertion of each of the following key-value pairs: (2, A), (2, C), (12, T), (5, Z). In the final diagram, draw all the fields and pointers of all the entries.