In the first parts of this lab, we will be creating our own implementation of the hashtable data structure for use in the Map ADT called MyHashMap in order to better understand their implementation and behavior.
We will be following along and implementing much of the functionality of Java’s HashMap<K, V> collection whose Javadocs can be found here. However, we will not directly implement the Map<K, V> interface because it requires more methods than we need for this assignment.
Notice that we actually have two generic types for this data structure: K is the class type of our keys and V is the class type for our values. For example, if I wanted to use a MyHashMap where the keys are Characters and the values are Integers (e.g., for counting how often individual characters appear in text), then my data structure would be a MyHashMap<Character, Integer>.
In Java, key/value pairs are stored together within Entry<K, V> objects. In particular, we will use Java’s SimpleEntry<K, V> class whose Javadocs can be found here. We can create new key/value pairs using the code:
SimpleEntry<K, V> entry = new SimpleEntry<K, V>(key, value);
and we can get the key and value from a SimpleEntry<K, V> entry using the code:
K key = entry.getKey();
V value = entry.getValue();
and we can change the key and value in a SimpleEntry<K, V> entry using the code:
entry.setKey(newKey);
entry.setValue(newValue);
In Visual Studio Code, open the provided MyHashMap.java file where we will implement a hashtable as a Map ADT. We have provided you with some starter code that will be explained below when it is relevant to your assignment instructions, and we have also already imported the other classes from Java that you will use.
ReadMe
As you are implementing your solutions, do not forget to include documentation using Javadocs! This is important practice to get into the habit of, and it will be a portion of your solution grade. The class itself (at the top), each instance variable, and each method should have a short Javadoc comment.
The starter code that we have provided you gives examples of the style you should use for your Javadocs.
Your MyHashMap class should have two private instance variables:
hashtable: an array of LinkedLists storing items of type SimpleEntry<K, V> that we will use as the bucket array of our hashtablesize: the number of key/value pairs stored as SimpleEntry<K, V> objects in our hashtable Rather than summing up the sizes of the individual LinkedLists in the hashtablebucket array, we will maintain this count as an instance variable (like we did for our Lists in earlier labs).ReadMe
Since our hashtable is an array of LinkedList objects, we will be implementing the chaining approach from lecture and the textbook.
Both of the instance variables should be private so that their access (especially assigning values) can be controlled through the MyHashMap class.
The MyHashMap class should have only one constructor: a public constructor that takes no parameters and creates values for the two instance variables. The initial size should be 0 since the MyHashMap starts empty, and the hashtable can be created by calling the provided createTable method with the INITIAL_LENGTH as its argument. This will make the bucket array for the hashtable with 11 buckets.
Next, we should implement three additional methods common to Collections in Java:
public int size(), which returns the number of key/value pairs stored in the MyHashMap and its hashtable
public boolean isEmpty(), which returns true if the MyHashMap is empty, else false
public void clear(), which removes all key/value pairs from the hashtable and resets the size to 0.
Hint
Since our hashtable is an array of LinkedLists, we can iterate through each LinkedList and call the clear() method of each to remove the SimpleEntry<K,V> objects storing all key/value pairs.
Ultimately, we will create unit tests to test each of the methods implemented in our class. However, we cannot do so until we implement the ability to get and put items, which we will do in the next two parts of the lab.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.