Please see the instruction, the hash_table.h file is provided. Please modify it and provide an extra makefile, thank you so much.

Description In the hash table implementation presented in class (on February 7), the number of buckets is fixed when the table gets instantiated. If we end up inserting many more items than there are buckets, the table becomes congested and we no longer get the "typical" O(1) time when adding, looking up, or removing an item. Dynamic Hashing Your task is to extend the hash table implementation to get dynamic hashing, that is dynamically resize the table based on the number of items it holds. You will also modify the constructor so that if no parameter is specified when the user instantiates a new hash table, then it uses a default size of 10 . The user should still be able to specify the number of buckets in the constructor if they desire. As discussed in class, the basic approach you should take is that after inserting a new item, check if the number of items is greater than the number of buckets (i.e., the table starts to become congested). If this is the case, you must 1. Allocate a new array of buckets (each holding a linked list) that is twice the size of the current array of buckets. 2. Iterate through all items in the old hash table, recompute the bucket they should occupy in the new array of buckets, and add the item to the list in that new bucket. To save space, you also need to shrink the table when it becomes too sparse. The basic approach you should take in this case is that after removing an item, check if the number of items is less than 1/4 of the number of buckets (using integer division) and the number of buckets is greater than the default size of 10 . If this is the case, you must 1. Allocate a new array of buckets (each holding a linked list). If the old number of buckets is B, then you should allocate max(B/2,10) buckets (using integer division). 2. Iterate through all items in the old hash table, recompute the bucket they should occupy in the new array of buckets, and add the item to the list in that new bucket. Note: to avoid memory leaks, it is important that your implementation deallocates any storage that is no longer being used. Your solution must build off of the file hash_table.h that is provided as part of the starter code. You can include C++ standard header files, such as algorithm. You can also add new private methods to the class if needed, but no public methods can be added. Make sure to add the proper function header when you (a) add a new private method; (b) modify an existing method. Your final implementation should work with the driver file we 4_test. cpp that is provided, without modification. We will be testing that your submitted hash_table.h file works with the original version of we4_test. cpp. The driver file reads the initial number of buckets from the standard input (the first line), instantiates an object of the HashTable class, and handles the following commands: - I e This command will insert a new element, an unsigned integer e, in the table. This will happen only if this element is not in the table. - Re This command will remove an element, an unsigned integer e, from the table. We promise we will not test this command to remove something that is not in the table. - Qe This command will look up an unsigned integer e, in the table and return either found or not found. - B This command will return the current size of the table, i.e., the number of buckets that constitute the table. - S This command will return the number of elements that are currently in the table. - STOP This command will terminate the execution of the driver. A Sample Interaction Below is the expected output of your program for the sample input. Sample Output Grading Comments - Style matters. Use appropriate comments, proper indentation, etc. Consult the style guide on eClass. - You must adhere exactly to the output specification: for example, if you output in the wrong order or print extra whitespaces then you will receive a deduction. The test centre must accept the output without any presentation error. - You were only given a few test cases in the test centre files. We will test your solution on additional test cases that adhere to the input specification. Submission Guidelines: Submit all of the required files according to the instructions for GitHub Classroom. Do not use compressed files or archives with GitHub Classroom. When you clone the repository, there should be a special directory called soln (this exact name) with the following files in that directory: - hash_table.h contains your implementation of the dynamic hash table. You may add new private methods or modify the existing public methods of the HashTable class, but you are not allowed to add new public methods. Recall that with template code, you cannot separate the implementation from the header. So it is acceptable to put implementations of functions with template arguments in this header file. - linkedlist.h contains the implementation of linked list. This file must remain unchanged but still be included in your submission. - dynarray.h contains the implementation of dynamic array. This file must remain unchanged but still be included in your submission. - we4_test. cpp is the driver file that reads data from the standard input processes commands, and calls public methods of the HashTable class. This file must be unchanged but included in your submission. This is the only . cpp file you will have in the soln directory. - your README (use this exact name) conforms with the Code Submission Guidelines. Create the file yourself and add it to the git repo. - your Makefile (use this exact name) that contains targets for compiling and linking your code. Create the file yourself and add it to the git repo (in the soln directory). It must contain the target we4_solution to build the final executable (called we4_solution) and the target clean to remove the object file and executable. You may add more targets in addition to these targets. Note that you will not be able to use the test center until you have a Makefile that correctly compiles your code and builds the executable file. The test center has its own Makefile (in the parent directory) that should not be modified. It uses your custom Makefile to build the executable. Other than the files originally provided via GitHub Classroom, and the files listed above, no other files should be submitted. Note that your files and functions must be named exactly as specified above. In your code, do not have any extraneous calls to input, output, or other I/O functions that might interfere with automated testing. A tool has been developed by the TAs to help check and validate the format of your submission, prior to your final commit to git. Run it via: \[ \text { python } 3 \text { submission_validator.py --help } \] to see abbreviated instructions printed to the terminal. You may also run [I from the main directory to validate the format of your submission. If your submission passes this validation process, and all validation instructions have been followed properly, you will not lose any marks related to the format of your submission. (Of course, marks can still be deducted for correctness, design, and style reasons, but not for submission correctness.) When your marked assignment is returned to you, there is a 7-day window to request the reconsideration of any aspect of the mark. After the window, we will only change a mark if there is a clear mistake on our part (e.g., incorrect arithmetic, incorrect recording of the mark). At any time during the term, you can request additional feedback on your submission. Marking Rubric: NOTE: The code must solve the problem algorithmically. If there is any hardcoding for the provided test cases, then zero marks will be given. This Weekly Exercise will be marked out of 100 for: - Correctness: Meets all specifications, generates no extraneous output, requires no unspecified input, has no memory leaks, and provides correct answers for the test inputs. Note: The output must match the given outputs exactly (e.g., whitespace, every period or character, formatting; read the description carefully) such that the Unix diff program cannot detect any differences. NOTE: Passing a test means having both the correct output and being algorithimically efficient (enough). - 70/70: Pass all of the provided and new (i.e., holdout) test inputs. Consideration will be made for documented reasonable design decisions, if the provided test inputs are handled correctly. - 40/70: Pass all of the provided test inputs - 20/70: Pass any of the provided test inputs - Style and Design: Part marks likely, as this is subjective. - 20/20: Meets all style and design requirements discussed in the Code Submission and Style Guidelines (on eClass), and contains a Makefile in the soln directory with the specified targets. - 10/20: Meets most (but not all) style and design requirements. - 5/20: Meets some (but not all) style and design requirements. Code Submission and Style Guidelines (on eClass) - README : Part marks possible. - 5/5: Correctly contains all of the required information, and in the right format, as described in the Code Submission and Style Guidelines, Chapter 2 (on eClass). - 0 to 4/5: Deductions for missing name, CCID, student number, course name, etc. NOTE: CCID is now required and marked. - Submission Validator: Pass the submission validator. - 5/5: Submission validator outputs VALIDATION SUCCEEDED. Otherwise, 0/5. As stated in the Course Outline, this is a Solo Effort assessment. Plagiarism detection tools, such as MOSS, might be used to find code common to multiple submissions or found on the Internet. / A hash table for storing items. It is assumed the type T of the item being stored has a hash method, eg. you can call item. hash(), which returns an unsigned integer. Think: the hash table is like a python set. Also assumes the != operator is implemented for the item being stored, so we could check if two items are different. If you just want store integers int for the key, wrap it up in a struct with a .hash() method and the != operator. Course: CMPUT 275 Zac Friggstad, 2021 */ \#ifndef_HASH_TABLE_H_ \#define_HASH_TABLE_H_ \#include "linked_list.h" \#include "dynarray.h" \#include template T> class HashTable \{ public: // creates an empty hash table with the given number of buckets. HashTable(unsigned int tableSize); HashTable (const HashTable & copy); HashTable ( ); HashTable & operator = ( const HashTable & rhs); // Check if the item already appears in the table. bool contains (const T\& item) const; // Insert the item, do nothing if it is already in the table. // Returns true iff the insertion was successful (i.e. the item was not there). bool insert(const T\& item); // Removes the item after checking, via assert, that the item was in the table. void remove(const T\& item); // Returns the number of items in the hash table. unsigned int size() const; // Returns the number of buckets in the hash table. unsigned int getBucketCount() const; // Returns a dynamic array containing the items in the hash table // (in no particular order). DynamicArray getItemsArray ( ) const; private: LinkedList table; // start of the array of linked lists (buckets) unsigned int numItems; // \# of items in the table unsigned int tableSize; // \# of buckets