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.