Assignment #4: Hashing

Due: Nov 16 before class

The Problem

In this assignment you will compare two implementations of Hash Tables using separate chaining. Thr first implementation is the standard version of Separate Chaining as described in class. The second implementation is a variant of Separate Chaining. It uses two hash functions and computes two hash values for any item. To perform a search, it searches the chains associated with both has values. To perform an insert, it always adds the new item to the shorter of the two chains associated with the two hash values. Your implementation needs to provide a method called showLengthDist that reports the average chain length, maximum chain length and the standard deviation of chain lengths. Your code should disable rehashing even if the load factor becomes high. No duplicates should be inserted. You will also need to run your program against my test program, which will test the following methods: insert, remove, contains, showLengthDist, with data of type Integer, String and Double (as in previous assignments.

Implementation Details

You will need two functional interfaces -- one for the hash table and one for the hash function as specified below:

package cop3530;
public interface MyHashTable {
    void insert (AnyType x); 
    void remove (AnyType x); 
    boolean contains (AnyType x); 
    boolean isEmpty ( ); 
    void makeEmpty ( );
    void showLengthDist ( );
}

and:

package cop3530;
public interface HashFunction {
    int hashCode( AnyType x );
}

The two classes SeparateChainingHashTable and TwoChoiceChainingHashTable should implement the interface MyHashTable and they would look like this:

package cop3530;
public class SeparateChainingHashTable> 
    implements MyHashTable
{
    public SeparateChainingHashTable( int size ) { /* Implement */ }
    public void showLengthDist( ) { /* Implement */ }
    /* Implement other public methods from interface here */

    private int myhash( AnyType x )
    /* Figure 5.7 from Weiss' book */
    
    private List [ ] theLists; 
    private int currentSize;
}

and:

package cop3530;
public class TwoChoiceChainingHashTable>
    implements MyHashTable
{
    public TwoChoiceChainingHashTable(int size, HashFunction hash2 )
    { /* Implement */ }

    /* Implement public methods from interface here */

    private int myhash( AnyType x )
    /* Figure 5.7 from Weiss' book */
    /* To be used as the first hash function */
    
    private List [ ] theLists; 
    private int currentSize;
    private HashFunction hash2;
}

You must use the following implementation for the second hash function to be used by the class TwoChoiceChainingHashTable:

package cop3530;
public class hashF2 implements HashFunction {
    public int hashCode( AnyType key ) {
        return key.hashCode() * key.hashCode();
    }
}

Duplicates should not be inserted. It should merely elicit an error message before moving on to the next command. The implementation of the method toString and the Iterator are optional. If the contains method is invoked on an empty MyHashTable, then you should simply return false. The output format for the method showLengthDist should be as shown below in the sample output:

Hash Table Size = 43
Number of items in Table = 192
Average chain length = 4.46
Maximum chain length = 14
Standard Deviation   = 2.36
-------------------------------

As in the previous assignment, the test program will be provided as a .class file, without any Java source, so it is important that you write sufficient test cases on your own to convince yourself that your logic works.

What to Submit

Submit your source code (all java files), all class files for the java files, the tester class file, and the result of running the class file that I provide. All of these should be zipped and one zip file (appropriately named) should be submitted. The zip file should represent the correct directory structure of the files needed to run. The following are suggestions to get the tester file to work: Regardless of whether you use and IDE (NetBeans, Eclipse) or not, all your class files for package cop3530 should be in one directory as shown below. Include your test class as shown below, i.e., in the directory classes. At this point your directory structure should look close to the following (although only the last 2 levels are relevant for our discussion here). You may have other files depending on your class structure.

Assignments/
    build/
        classes/
            cop3530/
                MyHashTable.class
                HashFunction.class
                SeparateChainingHashTable.class
                TwoChoiceChainingHashTable.class
            TestForAssign4.class
    src/
       cop3530/
           MyHashTable.java
           HashFunction.java
           SeparateChainingHashTable.java
           TwoChoiceChainingHashTable.java

Now open a shell window or a command prompt window, cd to directory classes mentioned above, and run the following command from the command line:

java -cp . TestForAssign4

The option -cp . suggests that the classpath is at . (i.e., the current directory). Remember not to include .class when referring to your tester class.