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

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.


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.


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:

Please don’t forget the Stevens honor pledge.