MapADT

The data structure that you will individually implement for project one is a Hash Table. You must develop the code for this assignment entirely on your own. If you encounter difficulties while working, you are encouraged to discuss general algorithms and debugging strategies with anyone you would like. If you feel that getting assistance will require someone else viewing your code, the course staff are the only people that you are allowed to share or show any part of your code with prior to the hard deadline for this assignment. You may not store or share your code in any way that another students can access. And you are not allowed to view or make use of any Hash Table code that is not written entirely by you.

HashTableMap Specifications

You must define a public class HashTableMap that implements this provided MapADT interface . Your implementation must:

• be left in the default package: ie. do not define it within a named package.
• be defined with two generic type parameters in this order: < KeyType, ValueType> which allow it to be used with different types of key and value pairings.
• include two constructors with the following signatures:
  • public HashTableMap(int capacity)
  • public HashTableMap() // with default capacity = 10
• use a private array instance field within your HashTableMap class to store key-value pairs.
• grow by doubling and rehashing, whenever its load capacity becomes greater than or equal to 80%. Define private helper methods to organize this functionality.
• store new values in your hash table at the index corresponding to the absolute value of your key's hashCode()) modulus the HashTableMap's current capacity. When the put method is passed a key that is already in your hash table (use.equals() to check for this equality), the put method should return false without making any changes to the hash table. The put method should only return true after successfully storing a new key-value pair.
• include a remove method that returns a reference to the value associated with the key that is being removed. When the key being removed does not exist, this method should instead return null.
• include a size method that returns the number of key-value pairs stored in this collection, and include a clear method that removes all key-value pairs from this collection.
• use chaining to handle hash collisions. You may make use of the java.util.LinkedLists class for this purpose.
• throw exceptions as indicated within the comments of the MapADT interface. You should make use of java.util.NoSuchElementException for this.
• NOT make use of any classes from java.util other than the two exceptions listed above: you may use java.util.Linked List, and java.util. NoSuchElementException.

TestHashTable Requirements

In addition to your HashTableMap.java implementation, you must develop and submit a test suite in a source file named TestHashTable.java. This test suite must include at least five distinct methods with the following names and signatures. Each of these methods should return true when the HashTableMap class that they run within behaves correctly, and false when any unexpected (buggy) behavior is detected. Each test should be designed to test a different feature of the HashTableMap implementation. Note that these methods should not throw exceptions, since any expected exceptions should be caught to verify the correct expected behavior, and any unexpected exceptions should be caught to allow your method to return false. Be sure to provide descriptive comments for each of these test methods, which describe the high-level functionality that they are designed to check for. Note that these should NOT be JUnit 5 tests for this assignment.

public static boolean test1() { /* test code here */ }
public static boolean test2() { /* test code here */ }
public static boolean test3() { /* test code here */ }
public static boolean test4() { /* test code here */ }
public static boolean test5() { /* test code here */ }