The goal for this lab is to implement a hash table that uses separate
chaining. The Map interface in Map.java specifies
the methods that should be provided by your HashTable class.
HashTable.java (Problem 1) to
link.StudentTest.java (Problem 2) to
link.The first thing you should do is complete the hash method. As you may recall, this should convert an object into an integer index into the hash table’s array. Java provides a hashCode() method for every object, which returns an integer between Integer.MIN_VALUE and Integer.MAX_VALUE, which you should use for this step.
You will also complete the following methods in the HashTable.java file, implementing the Map interface.
V get(K key) throws Exception
This method returns the value associated with the key, if there is one. Otherwise it throws an exception.
void put(K key, V value)
This method maps key to value in the table, overwriting any existing entry.
A later call to get with this
key should return this value.
void remove(K key)
This method removes any existing entry with the specified key in the table. A later call to containsKey with this key should return false.
boolean containsKey(K key)
This method returns true if there is an entry with the specified
key in the hash table, and returns false otherwise.
You will also need to implement the constructor for HashTable, in
which you will need to initialize the table. The constructor should
have one parameter, the initial table size:
public HashTable(int table_size);
As usual, you may create any helper methods that you find useful.
Write your test cases in StudentTest.java with the method named test(),
which should thoroughly test the hash table.
Test and debug your own code from Problem 1 locally and then submit both your code and your test cases to Autograder for grading.
The Autograder will apply your tests to buggy implementations of the HashTable class. You receive 1 point for each bug detected. The Autograder will also apply your tests to a correct implementation to rule out false positives.