P1W2: Hashtable Map Work Individually The data structure that you will individually implement for project 1 is a Hashtable. 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. But you are NOT ALLOWED to view any Hashtable implementations of others, and you are NOT ALLOWED to show or allow access to your implementation to anyone outside of the CS400 course staff. HashtableMap Specifications You must define a public class HashtableMap that implements this provided MapADT. 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: which allow it to be used with different key and value type pairings. include two constructors with the following signatures: public HashtableMap(int capacity) public HashtableMap() // with default capacity = 8 implement open addressing with a simple linear probe to handle hash collisions. It's likely to be helpful to create a helper class of your own to group together key-value pairs within a single object, so that you store these pairs within your hashtable's array. use exactly one protected single-dimensional array instance field. You can have additional fields of other types, but only one array. Note: You cannot instantiate an array with an associated generic type in Java. So you should instantiate the array for your hashtable using the raw type (without any generic specifications) and then cast to the complete type (including generics) before storing this reference in a protected instance field. Doing this produces an unchecked cast warning in Java that can either be ignored, or suppressed by adding the @SuppressWarnings("unchecked") annotation in front of the line of code with the cast. use open addressing with a simple linear probe to handle hash collisions. It's likely to be helpful to create a helper class of your own to group together key-value pairs within a single object, so that you can store these pairs within your hashtable's array. It may also be helpful to create one of these objects to use as a sentinel value to store in locations that old key-value pairs have been removed from. store new values in your hash table at the index corresponding to { the absolute value of the key's hashCode() } modulus the HashtableMap's current capacity. When the put method is passed a key that is null or is equal to a key that is already stored in your hash table, it should throw an IllegalArgumentException without making any changes to the hashtable. dynamically grow your hashtable by doubling its capacity and rehashing, whenever its load factor becomes greater than or equal to 70%. Define private helper methods to better organize the code that does this. Note that you can and should get rid of any markers indicating locations that key-value pairs have been removed from when growing this array. include a remove method that returns a reference to the value associated with the key that is being removed, and maintains the hashtable so that all other keyvalue pairs stored there can continue to be found. throw exceptions as indicated within the comments of the MapADT interface. You will make use of both java.lang.IllegalArgumentException and java.util.NoSuchElementException for this. Note that when checking keys for equality, you should check whether their content is the same using the .equals() method, rather than requiring the more strict == equality. NOT make use of any classes from libraries. The only class from java.util that you can use is the NoSuchElementException class mentioned above. HashtableMapTests Requirements In addition to your HashtableMap.java implementation, you must develop and submit tests in a source file named HashtableMapTests.java. These tests must include at least five distinct methods with the following names and signatures. Each should return true when the HashtableMap class that they are run with behaves correctly, and false when any unexpected (or buggy) behavior is detected. Each test should be designed to test a different feature of your HashtableMap implementation. These test methods should NOT throw exceptions, since any expected exceptions should be caught to verify correct expected behavior, and any unexpected exceptions should be caught and reported as faulty behavior (by returning false). These tests should be independent from one another, and should work equally well when run in any order. 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 test methods should NOT be JUnit5 tests for this assignment since that is a tool that we'll be covering in a future week. 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 */ }