Subversion Repositories programming

Ira Snyder
CS241 Section 01
Project #1: Open Hashing
Due: 10-22-2004

Purpose:
The purpose of this project is to implement an open hashing scheme in order
for us as students to better learn how hashing works. This program will also
help by showing us which hashing methods work the best.

How I modified the put() method:
In order to change the method that put() uses to choose the next position to
attempt to insert a key/value pair, I did two things. One, I added a new
private variable, int probeType, to the HashTable class. This allows me to
make a runtime call to the class to set this variable, which will select the
probing method to use. The second thing I added was a switch statement to
the nextProbe() method which decides which probe method to use based on the
value in the probeType variable (using a switch statement). Choosing the
probe method this way allows for easy automation of the driver program.

I also had to modify the put() method by adding a few print statements in
order to get the desired output.

For each run specifically:
run0: call HashTable.setProbeType(0), then run normally (Linear Probing)
run1: call HashTable.setProbeType(1), then run normally (Prime Probing p=3)
run2: call HashTable.setProbeType(2), then run normally (Prime Probing p=5)
run3: call HashTable.setProbeType(3), then run normally (Prime Probing p=7)
run4: call HashTable.setProbeType(4), then run normally (Prime Probing p=11)
run5: call HashTable.setProbeType(5), then run normally (Quadratic Probing)
run6: call HashTable.setProbeType(6), then run normally (Double Hashing)

Analysis of Output:

Best in order of least to most collisions:
Prime Probing p=3           8 collisions
Quadratic Probing           8 collisions
Double Hashing              9 collisions
Prime Probing p=7           11 collisions
Linear Probing              14 collisions
Prime Probing p=5           21 collisions
Prime Probing p=11          23 collisions

So, in terms of least collisions, Prime Probing p=3 and Quadratic Probing are
the best, and Prime Probing p=11 is the worst. However, analyzing the
printouts of where the values were inserted leads me to a different
conclusion. Based on the printouts, I believe that Quadratic Probing is the
best because it seems to work very well even when the load gets very high.
This is also true of Double Hashing. I think the result of Prime Probing p=3
performing very well is a consequence of the data set used. If many different
data sets were used, I believe that Quadratic Probing and Double Hashing would
show up as the best general probing methods (best in the majority of cases).