Homework 7: Hash Tables

The primary hash function will be simply modulo the table size, and we will take table sizes which are perfect powers of two, 2, 4, 8, 16, and so forth. The secondary hash function will give odd numbers 1, 3, ... , 11. The primary and secondary hash functions will use the Java hash codes for the objects, as returned by the hashCode() method defined for all objects.

We will make a hash table of strings. The strings will be read from a file and hashed into the table. Use tables of different sizes, and sample text files of different contents to test the quality of the hash functions. Come up with an average hash time as a function of load factor.

The following classes will get you started. You will need to finish up the insert and find routines and consider how to handle to delete routine. Test your project on a mix of finds, inserts and deletes.

• MyHashTable.java
• MyHashTableTest.java
• sampleinput.txt
• a program to scan for web servers; makes a good source of test input.

• There is a fast way to modulo 2^k which requires a single bit-wise and (&). Implement this.
• Try various table sizes (always 2^k for different k) with the following load factors: 20%, 40%, 60%, 80%. Discuss the rise of collisions as load rises. Compare to the formula 1/(1-load).
• Try both double hashing an single hashing. Single hashing can be done as a form of double hashing with the second hash function always returns 1. See if the hashing behaviour is worse with single hashing compared to double hashing.
• The sample input file is too small to test large table sizes. Create a larger data set and submit it with your programming results. I have written scannwww, a Java program that will scan the web for all URL's of a certain format, which you can use to create test files.
• Implement deletion.
• Note well: The submit directory's name should be MyHashTable