Assignment #5:

In this assignment you will implement a HashMap using separate chaining; however, you will allow two hash functions and always add new items to the shorter of the two lists suggested by the hash functions. Provide logic that returns an array with the distribution of the list lengths. You will also need to run against my test program.

The two hash functions are specified by the functional interface:

package cop3530;

public interface HashFunction<AnyType>
{
int hashCode( AnyType x );
}

The MyHashMap class looks like this:

package cop3530;

import java.util.Map;
import java.util.Iterator;

public class MyHashMap<KeyType,ValueType> implements Iterable<Map.Entry<KeyType,ValueType>>
{
    private HashFunction<KeyType> hash1;
    private HashFunction<KeyType> hash2;

    public MyHashMap( HashFunction<KeyType> h1, HashFunction<KeyType> h2 )
      { /* You must implement */ }

    public int size( )
      { /* You must implement */ }

    public void clear( )
      { /* You must implement */ }

    public ValueType put( KeyType k, ValueType v )
      { /* You must implement */ }

    public boolean remove( KeyType k )
      { /* You must implement */ }


    public ValueType get( KeyType k )
      { /* You must implement */ }

    public String toString( )
      { /* You must implement */ }


    public Iterator<Map.Entry<KeyType,ValueType>> iterator( )
    {
        return new Iterator<Map.Entry<KeyType,ValueType>>( )
        {
            public boolean hasNext( )
              { /* You must implement */ }

            public Map.Entry<KeyType,ValueType> next( )
            {
                final Node<KeyType,ValueType> theCurrent = current;

Map.Entry<KeyType,ValueType> nextItem = new Map.Entry<KeyType,ValueType>( )
                {  /* You must implement; access theCurrent here */ }
                };          

                // implement the rest of next, returning nextItem eventually,
            }

            private void advanceToNewList( )
              { /* You must implement */ }

            { 
                /* You must implement instance initialize */
            }

            Node<KeyType,ValueType> current;   // current node
int listNum;                       // current list #
        };
    }

    private static class Node<KeyType,ValueType>
    {
        Node( KeyType k, ValueType v, Node<KeyType,ValueType> n )
        { key = k; value = v; next = n; }

        public String toString( )
        { return key + "=" + value; }

KeyType key;
ValueType value;
        Node<KeyType,ValueType> next;
    }

    public int [ ] getLengths( )
      { /* You must implement */ }

private static final int DEFAULT_ARRAY_SIZE = 11;

    private Node<KeyType,ValueType> [ ] arr = null;
    private int theSize = 0;
}

Much of the logic was done in class for separate chaining implementation of MyHashSet. The main changes are:

1. You will use get and put instead of contains and add. If a key is added that already exists, the new value replaces the old value. put returns the prior value or null if this is the first occurrence of the key.

2. You will use two hash functions and add to the shorter list. It is a design decision if you want to maintain the list lengths or compute them every time.

3. Your iterator will return a Map.Entry object so you will also need an anonymous class that implements the Map.Entry interface. The main issue here, is that you should not access currentNode inside any of that implementation. Instead, copy currentNode into a final variable and access the final variable.

What to Submit

Submit complete source code and output of the test program.

You must also provide a writeup that briefly compares your list length distribution with using just a single (standard String) hash function.