CSC 132 Fall 2000
Lab 10
Due: end of lab period 30 November 2000
15 points

"Hash is fast food"

You will need to download three files to complete this lab. Two are from the eccentric download folder for Lab 10: Speedy.java and Sdriver.java. The third is the Statistic.java file from the eccentric download folder for Homework 1 solution.

Your assignment is to perform a simple study of hashtable efficiency. This will require a little programming and a little analysis.

The Programming: Speedy.java implements a simple hashtable class designed especially for this assignment. The hashtable will contain integer values, and the hashing method is provided. The class includes an insert method for placing values into the table (using open address hashing), and a probe method for determining how many probes in the hash table are required to find a given value. You are to implement the probe method based on the specifications given below. The probe method will be tested by the driver program and results output.

Here is the specification:
public int probe(int target)
Parameter: target - the element value to locate in the hashtable
Returns: If target was found, return number of probes required. If target was not found, negate the number of probes and return this negative value.

The Analysis: The driver program Sdriver.java will run through a automated sequence of hashing experiments. Each experiment uses a different load factor. Recall that load factor is the number of values stored in a hashtable divided by the hashtable capacity. The load factor is nonnegative but must be less than 1. The load factor will be varied from .10 to .98 in steps of .02. Each load factor (experiment) will produce one line of output containing: the load factor, the average number of probes requires to successfully find a given value, and the average number of probes that would have been required had a binary search tree been used instead of a hashtable (this is calculated using 1/2 log₂(N), where N is the number of stored values). Based on this raw data, you are to write and submit a short report commenting on:

1. Which load factor serves as a crossover point, e.g. above this point the binary search tree requires fewer probes on average?
2. At the crossover point, compare the average number of probes output with the theoretical estimate given by the formula 1/2 * ( 1 + ( 1 / (1 - loadFactor))).
3. Comment on the selection of .75 as the default load factor for the java.util.Hashtable class. What is the average number of probes at that point, both theoretically and approximated from your output?
4. Comment on the heuristic that says to set hashtable size to be 1.5 times greater than the expected number of values to be stored. What is the average number of probes at that point, both theoretically and approximated from your output?

How will you know if the output is correct? Here are several clues: the minimum number of probes is 1, the average number of probes will remain close to 1 until you get to a load factor above 0.3, and you can always estimate the expected value using the theoretical formula described in #2 above.

When finished, submit Speedy.java to your upload folder. Submit your report in a document called lab10analysis.xxx, where xxx is txt for a text document, rtf for an RTF document or doc for a Word document.

[ Assignments | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )