DESCRIPTION: In this lab you will implement a hash table with linear probing and perform simulations to observe its performance. The hash table will store integers. The hash function to be used is h(x) = 2%M (the remainder after dividing x by M), where M is the size of the hash table. The set of possible keys x is the set of positive integers representable by the int data type. You must write the Java classes HashTablelin, HashTableQuad and a class TestHashTable for testing and for measuring its performance. SPECIFICATIONS: Classes HashTablelin and HashTableQuad implement hash tables where collisions are resolved with linear and quadratic probing respectively. Each class must contain a field named table, of type Integer [], which is a reference to the array which stores the keys. There must be other fields in each class to store the size of the table, the number of keys stored in the table and the maximum load factor allowed. All fields in the classes must be private. Pay attention to update these fields when performing hash table operations (when necessary). Classes HashTablelin and HashTableQuad must contain at least the following constructor public HashTablelin(int maxNum, double load) - creates a HashTablelin object representing an empty hash table with maximum allowed load factor equal to load. The amount of memory allocated for the hash table should be large enough so that maxNum keys could be stored without its load fac- tor exceeding the value of parameter load. The size of the table should be the smallest prime number such that the above requirement is met. For in- stance, if maxNum=5 and load=0.4, then the size of the table should be at least 5/0.4 = 12.5. The smallest prime number satisfying the requirement is 13. public HashTableQuad (int maxNum, double load) is specified in the same manner as in HashTablelin Classes HashTablelin and HashTableQuad must each contain at least the following public methods: 1) public void insert(int n): Inserts the key n in this hash table if the key is not already there. Collisions are resolved using linear or quadratic probing (depending on class). If the insertion will cause the load factor to exceed the maximum limit prescribed for this table, then rehashing should be performed by invoking the method rehash(). 2) private void rehash(): Allocates a bigger table of size equal to the smallest prime number at least twice larger than the old size. Then all keys from the old table are hashed into the bigger table with the appropriate hash function and with linear or quadratic probing respectively. 3) public boolean is In(int n): Returns true if key n is in this hash table. It returns false otherwise. 4) public void printKeys(): Prints all keys stored in this table, in no partic- ular order. 5) public void printKeysAndIndexes(): Prints all keys stored in this table and the array index were each key is stored in increasing order of array indexes. The purpose of this method is mainly to be invoked in your test class for verifying that insertions are correct. 6) Accessor public methods (get methods) to allow the user to see the values of the fields relevant to the table (max load factor, number of keys, etc.) The test class has to be designed to carefully check that all specifications are met. For instance, you need to verify, among other things, that rehashing is performed when needed, that the size of the table is a prime number and it is selected as specified, that no duplicates appear in the table, etc. During testing instructive messages should be printed to clarify what is tested (i.e., your method performing the tests should print such messages). You may write additional methods in your HashTablelin and HashTableQuad classes to aid in testing, if necessary. Additionally, the test class must contain a static method to perform simulations to measure the average number of probes for successful search for both linear and quadratic probing. For each 1 (0,1), S, denotes the average number of probes for successful search in a table with load factor and size approaching oo. Note that the number of probes to find a key which is in the table is the same as the number of probes performed when the key was inserted. Thus the average number of probes for a successful search in a particular table can be determined by computing the average number of probes needed when the elements were inserted (by adding all numbers of probes and dividing by the number of elements in the table). You need to perform this measurement for load factors i = 0.1,0.2, ... ,0.9, for both linear and quadratic probing cases and output the results. For each load factor , allocate a hash table, insert at least 100,000 randomly generated numbers and compute the average number of probes needed. Repeat the test 100 times for a good average (i.e., have a loop with 100 iterations and then average again over all iterations). In order to perform the test ensure that the initial hash table size is large enough so that no rehashing is needed, and after all 100,000 keys are inserted the load factor is the required 1 (to do this, when creating the test object pass the number of tests, i.e., 100,000, and to the constructor). Note that the random number generator may create duplicates, and duplicates should not be inserted, so make sure that you properly count the number of inserted keys. In order to count the number of probes performed during an insertion (i.e., the number of table slots that are examined, including the one where the key is in- serted), write another public method in classes HashTablelin and HashTableQuad called public int insertCount(int n) which inserts and returns the number of probes required. The method which performs the measurements should also output the theoretical values of S, for linear probing, for comparison. Note that the theoretical values are given by SA = 3 (1+1=1). You should compute the run time and space complexity of all methods written and be prepared to justify them to the TA. NOTES: To get credit for the lab you have to demonstrate your code in front of a TA during your lab session. A 50% penalty will be applied for late demo. A 25% penalty will be applied if the demo is on time, but the electronic submission is late. SUBMISSION INSTRUCTIONS: NO REPORT IS NEEDED. Submit the source code for each of the classes HashTablelin, HashTableQuad and TestHashTable in a separate text file. Include your student num- ber in the name of each file. For instance, if your student number is 12345 then the files should be named as follows: HashTablelin12345.txt, TestHashTable12345.txt, etc. Submit the files in the Assignments Box on Avenue by the end of your designated lab session. BONUS: A bonus of 0.5% of the course mark will be awarded if the test class also contains a method to measure the average number of probes for unsuccessful search with linear probing Ux, for each = 0.1,0.2,...,0.9. Each average should be computed over at least 100,000 searches (for randomly generated numbers) in a table with at least 100,000 keys randomly generated. Make sure that you only count the unsuccessful searches (i.e., when the key is not in the table). Your method should also output the theoretical value of each U, for linear probing, given by UX 1 1+ (1 - 1)