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 project, but the overal structure of our data will be very different. Instead of maintaining a 'sorted' structure and using the sort 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 particular for this project, we will again be implementing the MapSet interface (no changes from the previous project).

HashMap

This class will be a Hash Map that implements the MapSet methods. This time, we don't necessarily need our keys to be comparable, so we can use a class declaration such as

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

Design your own implementation of a hash map. It is up to you whether or not to use the default hash function provided by Java, it is up to you how to handle collisions, and it is up to you to decide how to deal with collisions. Chaining uses a data structure such as a linked list at each entry in the hash table so multiple entries can be stored at each position. Probing 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.

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, along with one extra remove method. However you must maintain the following rule for your data structure: let n denote the size of your HashMap, let f denote the load factor and let C denote the capacity of the table; except for n smaller than the initial capacity, it must hold that f³C ≤ 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/f. 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 HashMap(): calls the following constructor with a reasonably chosen starting capacity.
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 as a field.
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.

CHECK-IN

Note that for this project, you actually have a two week deadline. However: you are required to have this lab finished by Sunday 11/6. It will be worth 5 of the overall 30 points; I am going to write a simple tester for the data structure that assumes you have the methods built as described. I strongly recommend that you test your methods on your own prior to submission of the lab.

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