Putting Values

As our second main functionality, we will implement the ability to insert values into a MyHashMap based on their corresponding key.

However, before we implement such a put method, we need to create a couple more helper methods that will simplify our implementation.

insert Method

Since we are using SimpleEntry<K, V> objects to represent a key/value pair, we want to insert a SimpleEntry<K, V> object in our hashtable. For this, we will implement a private insert helper method that takes a SimpleEntry<K, V> entry as a parameter and behaves as follows:

1. Gets the key for the entry using its getKey() method and calculates the appropriate index as in Step 1 of the find method from Part 2 of the lab.

2. Gets the appropriate LinkedList from the hashtable using the index calculated in Step 1.

3. Adds the given entry to the LinkedList found in Step 2.

Here, we assume that the key of the given SimpleEntry<K, V> is not already in the hashtable.

resize Method

As we insert more and more key/value pairs into our hashtable, we increase the likelihood that two keys collide by having the same index into the hashtable’s bucket array based on their (different) hashCodes. Since we are using chaining to handle collisions, the runtime of our methods will increase as the number of collisions also increases.

To minimize the risk of collisions, we will resize the hashtable once the size of the MyHashMap reaches a predetermined percentage of the number of buckets in the hashtable’s bucket array. Implement a private resize method that takes no parameters, returns nothing, and behaves as follows:

1. Save the old hashtable as a different variable

2. Create a new array for the hashtable instance variable using the provided createTable method, passing in double the length of the old hashtable so that the size is at least doubled (n.b., it will actually be the next prime number after double the old length).

3. Iterate through every SimpleEntry<K, V> in every LinkedList in the old hashtable and call put to re-hash and re-insert the key/value pairs.

put Method

In Java, inserting a new key/value pair is accomplished through the method:

public V put(K key, V value)

If the key was already in the MyHashMap, then the method returns the previous value stored for that key, else it returns null. The pseudocode for this method is:

1. Use the find method developed above to look up whether key was already in the MyHashMap

2. If find returns a SimpleEntry<K, V> object because key was already in the HashMap, save the previous value from the SimpleEntry<K, V> and change the value to the value passed into the method using SimpleEntry’s setValue(value) method

3. If find instead returned null because key was not already in the HashMap, then we need to create a new SimpleEntry<K, V> storing the given key and value that were arguments to the put method. Call the insert helper method described above, and increase the size of the MyHashMap since a new key was inserted.

4. Next, check whether we need to resize the hashtable so that we can minimize the risk of collisions. This should occur whenever the size of the MyHashMap is greater than LOAD_FACTOR times the current length of the hashtable.

5. If the key was already in the HashMap, return the old value saved in Step 2. Otherwise, return null

Testing the put Method

Before moving on to the next part of the lab, we should create unit tests to verify our implementation so far and help us find and remove any bugs. As in previous labs, we can create a Java file that will contain our unit tests by right clicking anywhere in the MyHashMap.java file and selecting “Source Action” from the right click menu. Then, select “Generate Tests”. Use the default name proposed by the IDE of MyHashMapTest. Next, it will prompt you with what methods you want to create tests for.

Inside the newly created MyHashMapTest.java file, create a unit test verifying that the put method works properly. As one strategy, you could:

1. Create a new MyHashMap<String, Integer> instance
2. Save a number value for a new String key and make sure that the put method returns null since the key was new
3. Save a new number value for an existing String key and make sure that the put method returns the previous value stored for that key

You can also now create unit tests for your get method described in Part 2 of the lab, as well as the size, isEmpty, and clear methods described in Part 1 of the lab.

Committing Your Progress

Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.