CS231

Hash Map

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

Tasks

Testing

As always, as you are coding up this project write tests for each class you create exercising the public methods implemented in this class.

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:

An int size
An array of Nodes (Node[])
A double storing the maximal loadFactor, double maxLoadFactor

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

public HashMap(): calls the following constructor with a reasonably chosen starting capacity (Java uses 16).
public HashMap(int capacity): calls the following constructor with a reasonable load factor (Java uses .75).
public HashMap(int capacity, double loadFactor): initializes the HashMap with the given capacity and stores the given loadFactor.

The HashMap methods

You should probably have the following two private methods:

private int capacity(): this method returns the length of the array handling this map. Note that this is not necessarily the number of items actually stored in that array; there can (and should) be many empty slots.
private int hash(K key): this method should return the index of the underlying array in which the given key should be stored. A reasonable definition for this method could be
```
private int hash(K key){
    return Math.abs(key.hashCode() % capacity());
} 
```
but as mentioned above you are free to implement a different hash method if you so desire.

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.

public int size(): returns the size.
public void clear(): resets fields to default values
public V put(K key, V value): Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. Does nothing if value is null. Returns the previous value associated with key, or null if there was no mapping for key.
public V get(K key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
public boolean containsKey(K key): Returns true if this map contains a mapping for the specified key to a value.
public V remove(K key): Removes the specified key (and its associated value) from this mapping and returns the value it was mapped to.
public ArrayList<K> keySet(): Returns an ArrayList of all the keys in the map in no particular order.
public ArrayList<V> values(): Returns an ArrayList of all the values in the map in the same order returned by keySet()
public ArrayList<KeyValuePair<K, V>> entrySet(): Returns an ArrayList of each KeyValuePair in the map in the same order as the keys as returned by keySet().
public String toString(): Returns a String that represents the HashMap.
public int maxDepth(): returns the size of the biggest bucket (the number of items in the bucket with the most items)

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