CS 284-A Data Structures — Spring 2022

HW5: Chained Hash Maps

We’ll be defining a chained hash map in Java. Call your class ChainedHashMap. Here’s the interface we expect you to implement:

package cs284;

public interface Map<K, V> extends Iterable<Entry<K, V>> {
  public int size();
  
  public int capacity();
  
  public int rehashes();
  
  public int[] bucketSizes();
  
  public V get(K key);
  
  public boolean containsKey(K key);
  
  public V put(K key, V val);
  
  public V remove(K key);
}

Where we define Entry<K, V> as:

package cs284;

public interface Entry<K, V> {
  public K key();
  public V value();
}

You can download Map.java and Entry.java, but you may not make any changes to those files. If you include them in your final upload, we will overwrite them with our definitions.

You will have to design and implement hash map yourself. Make sure you implement Map<K, V>. You should not try to implement java.util.Map. You may not use any predefined notion of set (e.g., HashSet) or map (e.g., HashMap, HashTable) in your code. You may use other features, like the convenience methods in java.util.Objects and java.util.Arrays and sequential collections like LinkedList or ArrayList.

Core methods

• You must have a constructor that takes no arguments and creates an empty map. You will fail to compile or fail the tests with a grotesque exception if you don’t provide this contructor.
• size() returns the number of entries in the map; should be O(1)
• capacity() returns the size the of the underlying array, which should start at 64; should be O(1)
• rehashes() returns the number of times the array has been resized and all of the hashes recomputed; should be O(1)
• bucketSizes() should return an array indicating the number of values in each bucket; should be O(k) where k is the current capacity
• put(K key, V val) takes some key, key, and updates the hash map to map key to val; should be O(1) in expectation
  • Return the old mapped value if key already maps to something
  • Return null if key doesn’t map to anything
• get(K key) takes some key, and finds the value val such that key is mapped to val; should be O(1) in expectation
  • You should return null if key doesn’t map to anything
• containsKey(K key) should return true if something key maps to a value and false otherwise; should be O(1) in expectation
• remove(K key) should remove the mapping for key (if it exists); should be O(1) in expectation
  • Return the old mapped value if key maps to something
  • Return null if key doesn’t map to anything

When we say O(1) in expectation, we mean that you will of course have to traverse a bucket, but we expect all of the buckets to be lists of short length, and so the traversal is effectively constant time.

Implementing Iterable<Entry<K, V>>

You should implement Iterable<Entry<K, V>>, i.e., you must also implement a public method Iterator<Entry<K, V>> iterator(), which should return an iterator that yields each entry in the hash map in turn. It doesn’t matter what order the entries come in, but no entry should appear more than once.

Null keys

Your hash map should support null keys. You may find the Objects.hashCode(Object o) method useful.

Rehashing

You should rehash when the load factor is greater than 70%, i.e., size() > capacity() * 0.7. When you rehash, you should double the size of the underlying table.

Grading

As usual, there will be an autograder to test your code. You are free to define other helpers, but you must meet the public specification above for your code to compile. You may not alter the public spec. It’s okay if you submit your Map.java and Entry.java files, but we will ignore them and overwrite them with ours.

Our tester evaluates several tricky properties:

• You rehash at the correct rate, tracking size correctly.
• Objects with the same hash go to the same bucket.
• Keys can be overwritten in arbitrary orders.
• Keys can be null.

Please don’t forget the Stevens honor pledge.