Assignment #5: Hash Tables

Covers

Hash tables, Java programming

Basic problem

The Standard libray class TreeMap assumes that the objects are either comparable, or that there is a comparator function object that can be used to order the objects. As such, one can create a TreeMap of String objects in which "hello" and "HeLlO" are considered the same in the TreeMap. Unfortunately, there is no way to achieve this behavior in HashMap. This assignment asks you to write a basic implementation of cop3530.HashMap, and then add a mechanism that allows the user to construct a cop3530.HashMap with an equals and hashCode that will be used instead of the normal defaults.

Specification of Alternate equals and hashCode

Your cop.3530 HashMap class should implement the following functionality: 

package cop3530;

public interface Map<KeyType,ValueType> extends Iterable<Map.Entry<KeyType,ValueType>>
{
    ValueType get( KeyType k );
    ValueType put( KeyType k, ValueType v );

    int size( );
    void clear( );
    boolean isEmpty( );


    interface Entry<KeyType,ValueType> extends java.util.Map.Entry<KeyType,ValueType>
    {
    }

    Iterator<Map.Entry<KeyType,ValueType>> iterator( );
}
Provide a public interface in package cop3530 as follows: 
package cop3530;

public interface HashingFunction<T>
{
    int hashCode( T obj );
    boolean equals( T lhs, T rhs );
}
The HashMap class has an implementation that starts something like: 
   
public class HashMap<KeyType,ValueType> implements Map<KeyType,ValueType>
{
    public HashMap( )
      { /* Implement */ }

    public HashMap( double maxLoad )
      { /* Implement */ }

    public HashMap( HashingFunction<KeyType> hf )
      { /* Implement */ }

    public HashMap( HashingFunction<KeyType> hf, double maxLoad )
      { /* Implement */ }

     ...

    private HashingFunction<KeyType> hashFunc;
    private double loadFactorLimit;
}
HashMap methods consult the HashingFunction if one is provided, or uses the standard equals and hashCode if the HashMap is constructed without a HashingFunction. You implementation should also include a toString. In writing the seaprate chaining hash table, it is expected that you will use an array of singly linked lists, and that as insertions occur and the table becomes more loaded, the table will be appropriately resized in accordance with the the load factor limit.

What To Submit

Submit complete source code and run against a test program that I will provide.