Hash Map Assignment

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;    }  }
  @SuppressWarnings("unchecked")  private Node<K, V>[] table = new Node[10];  private int numElems = 0;

Equality Checks

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.

Trailing Pointer

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

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.

The keySet

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.

Higher-Order Methods

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

Test Rubric

Put your unit test in the test folder. When you run gradle test it will generate test coverage. That is put in the file app/build/jacocoHtml/csci2320/index.source.html. The number of points you get depends on your coverage of the files where you are adding code. Full points for 95% coverage or better.  Half points for 90-95% coverage. Quarter points for 80-90% coverage.

Speed Test

You can run the speed test that I will use by running gradle run and entering "speed".  The output will be different at different times and on different computers, but on a given computer you should be able to check when you make changes that make it run faster.