MyHashMap

Required Methods

Your MyHashMap class must have the below methods. If you are curious abou the documentation or what the below methods do, consule the Java documentation.

• clear
• containsKey
• containsValue
• get
• isEmpty
• keySet
• put
• remove - note the Java HashMap class has two versions. You only need to implement the one with the signature: remove(key).
• size
• printTable

The only method not taken from the Java documentation is printTable. printTable() should output how many conflicts occur at each bucket and list the keys in that bucket. No matter what, your hashTable should always have 8 buckets! An example output for printTable is shown here:

Index 0: (0 conflicts), []
Index 1: (0 conflicts), []
Index 2: (0 conflicts), []
Index 3: (0 conflicts), []
Index 4: (0 conflicts), []
Index 5: (0 conflicts), [ExampleKeyX, ]
Index 6: (0 conflicts), [ExamplekeyY, ]
Index 7: (0 conflicts), []
Total # of conflicts: 0

Implementation

In general, there are multiple ways to implement a hash map. Here are three:

• A linked list that contains a linked list for each bucket (2d linked list)
• An array that contains an array for each bucket (a 2d array)
• An array that contains a linked list for each bucket.

However, since you are implementing a generic hash table in Java and generics are problematic in arrays, we recommend you use an ArrayList of linked lists. The linked lists can be the Java LinkedList class or your own linked list implementation where the key, value pairs link to each other, whatever your prefer.

Your hash table implementation should be called MyHashMap.

Hash Function

Here is the code for the hash function. You can and should use this exact code in your project. Make sure you understand what it is doing and how it works.

private int hash(K key) {
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return Math.abs(index);
}

Collisions

This hash map will use chaining to handle the collisions of elements. Your hash map sould only have 8 buckets! Collisions will happen.

PUT the (key, value) pairs at the FRONT of the list in the bucket.

If the same key is passed in with a different value, do the value update in place.

PA8PublicTestCases.java

import static org.junit.Assert.*;
import org.junit.Test;

public class PA8PublicTestCases {
@Test
public void testExample1ContainsKey() {
MyHashMap< Integer, Integer> map = new MyHashMap<>();
map.put(1, 2);
assertEquals(true, map.containsKey(1));
}

@Test
public void testExample2ContainsKey() {
MyHashMap< String, Integer> map = new MyHashMap<>();
map.put("1", 2);
assertEquals(false, map.containsKey("2"));
}
}

HashNode

public class HashNode< K, V>
{
private K key;
private V value;

private HashNode< K, V> next;

public HashNode(K key, V value)
{
this.setKey(key);
this.setValue(value);
}

public K getKey() {
return key;
}

public void setKey(K key) {
this.key = key;
}

public V getValue() {
return value;
}

public void setValue(V value) {
this.value = value;
}

public HashNode< K, V> getNext() {
return next;
}

public void setNext(HashNode< K, V> next) {
this.next = next;
}