It is of course possible that two keys we want to insert into the hash table hash to the same value. It is a consequence of the Birthday Paradox $($en$.$wikipedia.org$/$wiki$/$Birthday$\_$problem$)$ that this will be far more likely than what our intuition might suggest. As a result, we need a way of distinguishing between keys with the same hash value. There are various methods to resolve collisions. For this assignment, you will be implementing a hash table with linear probing to resolve collisions. When two keys hash to the same index, linear probing searches the table for the closest following free location and inserts the new key there. $4.$ Table resizing It can be shown $($when you take CMPT $204,$ you may be asked to actually show it$)$ that hash tables maintain an average O$(1)$ time complexity for inserts and lookups only so long as the table is no more than $2/3$ full. Having fewer empty spaces increases the chance of collisions, which leads to longer probing times. Since your hash table needs to store an arbitrary number of keys and values, this means the size of your table may have to grow to accommodate additional inserts. To do so$,$ your hash table will have to keep track of the current number of elements in the table and its capacity. When the load ratio exceeds $2/3$ on an insert, the ht$\_$insert function will trigger a table resize operation. When this happens, additional memory needs to be allocated for the larger table. Consider what is the most practical solution: resizing the current array, or creating a new larger array. One of your design decisions is where to store the table capacity and current number of elements. Question: what will need to happen to all the keys and values already inserted into the hash table? Will they reside in the same position as before the resize operation took place? In your design document answer this and explain what needs to happen during resizing. $5.$ Data Structures In your design document, indicate what data structure you will use to represent your hash table, and what constitutes an entry in the table. Decide what information will be stored in each entry for a key$/$value pair. What will be the chosen datatype for keys? What will be the chosen datatype or data structure for values? This decision might be best made after reading the specifications of the postal code collator program below. Provide type declarations as appropriate, and describe at a high level how they will be used in insertion, lookup, and deletion operations.