Question 3: Hash Tables (19 marks) a) (4 marks) Suppose a hash table of size 7 is initially empty. If quadratic probing is used to resolve collisions, determ ine the final size of the hash table after 20 items are inserted b) (6 marks) Using linear probing to resolve collisions, insert the values 54 71 24 30 82 into an empty hash table of size 6. Assume that the hash function h simply reverses the digits of the given value. For example, h(68) returns 86. Show the hash table after each insertion. c) (9 marks, optional) Consider the (partial) definition of HashTable where only the keys are stored and where linear probing is used to resolve collision. public enum TStatuS (EMPTY, FULL, DELETED) public class HashTable TKey> private class Entry public TKey Keyget; set) Assume that GetHashCode)is defined for TKey public TStatus Status fget; set) private Entryl] T; private int size // Table of entries I/ Capacity of the hash table I/ Creates an empty hash table T of size public HashTable (int size) {..\ // Reduces T to half its size and then rehashes its remaining entries public void Shrink () HashTable A; Reference to the old hash table I/ Starting at index i, returns the next available index (EMPTY/DELETED) private int Linear (int i) ..) Inspired from class, suppose that the hash table is reduced to half its size once enough entries are removed (for instance, when only 10% of the table is FULL). Using only the methods and data members provided, complete the method Shrink which reduces T to half its size and then rehashes its remaining entries Question 3: Hash Tables (19 marks) a) (4 marks) Suppose a hash table of size 7 is initially empty. If quadratic probing is used to resolve collisions, determ ine the final size of the hash table after 20 items are inserted b) (6 marks) Using linear probing to resolve collisions, insert the values 54 71 24 30 82 into an empty hash table of size 6. Assume that the hash function h simply reverses the digits of the given value. For example, h(68) returns 86. Show the hash table after each insertion. c) (9 marks, optional) Consider the (partial) definition of HashTable where only the keys are stored and where linear probing is used to resolve collision. public enum TStatuS (EMPTY, FULL, DELETED) public class HashTable TKey> private class Entry public TKey Keyget; set) Assume that GetHashCode)is defined for TKey public TStatus Status fget; set) private Entryl] T; private int size // Table of entries I/ Capacity of the hash table I/ Creates an empty hash table T of size public HashTable (int size) {..\ // Reduces T to half its size and then rehashes its remaining entries public void Shrink () HashTable A; Reference to the old hash table I/ Starting at index i, returns the next available index (EMPTY/DELETED) private int Linear (int i) ..) Inspired from class, suppose that the hash table is reduced to half its size once enough entries are removed (for instance, when only 10% of the table is FULL). Using only the methods and data members provided, complete the method Shrink which reduces T to half its size and then rehashes its remaining entries