For this assignment, you will write a Map based on a hashtable. I implemented mine with an array of singly-linked lists. The array is basically an array of head pointers. My setup for this looked like the following. Note that the use of new doesn't include the generic types. This gets around the fact that you can't make arrays of generics in Java. Because the type of table is specified, this doesn't have implications elsewhere in the code.
private static class Node<K, V> { K key; V value; Node<K, V> next; Node(K key, V value, Node<K, V> next) { this.key = key; this.value = value; this.next = next; } }Be careful when comparing keys to use .equals instead of ==. If you don't recall this from CS2, == on object types does an identity check. It tells you if the two objects are the same object at the same location in memory. The .equals method will compare their contents to see if they have the same value. If you ever do something like key1 == key2 it will cause errors in some situations, likely in my tests, even if not yours.
Because the code uses a singly-linked list, insert and remove need to know the node before the one with the matching key. This winds up being the last node in the list when there is no match. To do this, the standard approach is to keep track of a "trailing" pointer that goes one step behind the rover. It starts at null and before you set rover = rover.next you set the trailer to be rover.
The iterator works as we discussed in class. My one note is that mine isn't an anonymous inner-class like the ones we've written before. Instead, it is a named, non-static inner-class. That allows me to have a constructor that advances the values to the first valid node.
For the keySet I was able to use an anonymous inner-class. Not that I gave you a Set.java file. If you accidentally import java.util.Set it won't work, so make sure you don't have that import. It has three methods in it and it is basically a wrapper around calls to the HashMap. So it makes liberal use of calls like HashMap.this.size(). One of the methods is iterator(). That method contains its own anonymous inner-class that includes the following private data.
private Iterator<KeyValuePair<K, V>> iter = HashMap.this.iterator();Note that I'm reusing the iterator I already wrote for the HashMap, and I only return the key instead of the full KeyValuePair.
There are some minor variations in the higher-order methods. I got rid of the mutating ones to save you time. I replaced takes and drops with the logical exists and forall.
For the following, assume the following declaration, which is working code from one of my tests.
var hash = HashMap.of( Map.kvp("abc", 3), Map.kvp("xyz", 19), Map.kvp("bob", 16), Map.kvp("jill", 51), Map.kvp("pat", 32) );In the examples below I'm using an arrow to indicate a key/value pair. This would be valid in Scala. The Java way is just too much more verbose.
mapValues
hash.mapValues(v -> v*2) ====> ("abc" -> 6, "xyz" -> 38, "bob" -> 32, "jill" -> 102, "pat" -> 64)
filter
hash.filter(kvp -> kvp.value() % 2 == 0) ====> ("bob" -> 16, "pat" -> 32)
hash.filter(kvp -> kvp.key().length() > 3) ====> ("jill" -> 51)
find
hash.find(kvp -> kvp.key().length() > 3) ====> Optional.of("jill" -> 51)
hash.find(kvp -> kvp.value() > 100) ====> Optional.empty
fold (not directional as order is "random")
hash.fold(0, (sum, kvp) -> sum + kvp.value()) ====> 121
exists
hash.exists(kvp -> kvp.value() == 16) ====> true
hash.exists(kvp -> kvp.key().length() < 3) ====> false
forall
hash.forall(kvp -> kvp.value() < 100) ====> true
hash.forall(kvp -> kvp.value() < 40) ====> false
Your tests need to include calls to all methods.
Your tests need to include at least one with enough data to make your array grow.