Hash Map

The goal of this lab period is to build a Hash Map (AKA Hash Table).


Tasks

We have supplied you with a partial HashMapTester that you will use for the lab checkpoint. You are expected to complete the remainder of the tester, as described in comments in the code, as you're working on your HashMap implementation. You can and should use it to test your code. We will evaluate your code against a completed version of the tester to grade it (our version, not yours!), and we will grade you on whether you filled in this tester. To run it, you will need to implement everything in the MapSet interface. For methods you haven't implemented yet, define the method, and return a placeholder value (e.g. null, -1, etc.).

MapSet

This week, we will be building a Hash Map that maps a set of keys to specific values. This is exactly in parallel to the previous lab, but the overal structure of our data will be very different. Instead of maintaining a 'sorted' structure and using the comparator to add and get our keys, we will calculate exactly where we want to put them and use that value to add and get them in O(1) time (in expectation, given some 'nice' assumptions).

In particular for this project, we will again be implementing the MapSet interface (no changes from the previous lab).

HashMap

This class will be a Hash Map that implements the MapSet methods, so we can use a class declaration such as

public class HashMap<K, V> implements MapSet<K, V>

This lab will guide you through the design of a HashMap that uses separate chaining and Java's built-in hashCode method to decide where to place the inserted objects. Other implementations of a HashMap are possible and are left as extensions. For example, you could implement Probing, which allows only a single value to be stored at each location in the hash table and uses probing to store colliding keys in a different location.

The Nodes

To implement chaining, we'll use an inner Node class. This slightly reduces the overhead from using a full LinkedList object.

The Node class should look pretty similar to last week's BST-Nodes, only this time instead of managing a left and right pointer, we'll treat it more like a singly linked list and only record a next pointer. The main suggestion I have here is to make your Node class extend the KeyValuePair class to more easily take advantage of their methods.

The HashMap fields and constructors

The HashMap class should manage the following fields:

To decide the initial values of these fields, you should implement the following constructors:

The HashMap methods

You should have the following methods:

The rest of the methods you need to create are the methods inherited from the MapSet interface. However you must maintain the following rule for your data structure: let n denote the size of your HashMap, let f denote the maximal load factor and let C denote the capacity of the table; except for n smaller than the initial capacity, it must hold that fC/4 ≤ n ≤ fC. Consider what happens when you add a new KeyValuePair into your mapping: if its size increases and now is greater than fC, you can increase the capacity to C * 2. Think about what the otherside of this coin looks like when we call remove. Of course, by resizing the array the KeyValuePairs might no longer be in the right locations, so you'll need to make sure that it gets re-inserted into the new array correctly.

When you are done, you can proceed to the project.