The binary search tree map from the last lab had faster add and remove operations than the sorted list map, but only if the keys of the map were randomly distributed. Another map implementation with even better performance with randomly distributed keys is a hashtable. In this lab you will implement a simple version of a hashtable map.
The file HashtableMap.java contains the outline for a hashtable based implementation of a map. It contains all of the same methods as the two previous Map classses, get, put, and remove. It doesn't, however, have a search method like the other two map classes. Instead it has a hash method that can calculate the index of an entry by using a key's hashCode method. Begin by implementing the private method hash. This method should be used by the get, put, and remove methods. It should use either division your modulo to to calculate indices. The put method should call the hash method to find the index of the linked list to which the new key-value pair should be added. The put method will also need to call the rehash method if the load factor of the hashtable exceeds the maximum threshold. Before writing the rehash method test the put method by writing a small test program. It may help to write the toString method. When the put method is working correctly without rehashing, write the rehash method and call it appropriately in the put method. Be sure to thoroughly test before proceeding.
Next, complete the get method. It should call the hash method to find the index of the linked list that should contain the key. If the linked list has an entry with the correct key, then it should return the value of the entry. If the linked list does not have the correct key, then it should return null. Before proceeding, be sure to test the get method.
Finally, complete the remove method. This method begins like the other three methods by calling the hash method to find the linked list that should contain the key. If the linked list does not contain the correct key, the method should do nothing. If, however, the key is in the linked list, the entry should be removed. This method does not need to rehash if the load factor is small. Remember to code in small pieces and test thoroughly.
To submit your code: Tar your lab12 directory and submit your code on the course Inquire site.