| 18 |
irasnyd |
1 |
Ira Snyder
|
|
|
2 |
CS241 Section 01
|
|
|
3 |
Project #1: Open Hashing
|
|
|
4 |
Due: 10-22-2004
|
|
|
5 |
|
|
|
6 |
Purpose:
|
|
|
7 |
The purpose of this project is to implement an open hashing scheme in order
|
|
|
8 |
for us as students to better learn how hashing works. This program will also
|
|
|
9 |
help by showing us which hashing methods work the best.
|
|
|
10 |
|
|
|
11 |
How I modified the put() method:
|
|
|
12 |
In order to change the method that put() uses to choose the next position to
|
|
|
13 |
attempt to insert a key/value pair, I did two things. One, I added a new
|
|
|
14 |
private variable, int probeType, to the HashTable class. This allows me to
|
|
|
15 |
make a runtime call to the class to set this variable, which will select the
|
|
|
16 |
probing method to use. The second thing I added was a switch statement to
|
|
|
17 |
the nextProbe() method which decides which probe method to use based on the
|
|
|
18 |
value in the probeType variable (using a switch statement). Choosing the
|
|
|
19 |
probe method this way allows for easy automation of the driver program.
|
|
|
20 |
|
|
|
21 |
I also had to modify the put() method by adding a few print statements in
|
|
|
22 |
order to get the desired output.
|
|
|
23 |
|
|
|
24 |
For each run specifically:
|
|
|
25 |
run0: call HashTable.setProbeType(0), then run normally (Linear Probing)
|
|
|
26 |
run1: call HashTable.setProbeType(1), then run normally (Prime Probing p=3)
|
|
|
27 |
run2: call HashTable.setProbeType(2), then run normally (Prime Probing p=5)
|
|
|
28 |
run3: call HashTable.setProbeType(3), then run normally (Prime Probing p=7)
|
|
|
29 |
run4: call HashTable.setProbeType(4), then run normally (Prime Probing p=11)
|
|
|
30 |
run5: call HashTable.setProbeType(5), then run normally (Quadratic Probing)
|
|
|
31 |
run6: call HashTable.setProbeType(6), then run normally (Double Hashing)
|
|
|
32 |
|
|
|
33 |
Analysis of Output:
|
|
|
34 |
|
|
|
35 |
Best in order of least to most collisions:
|
|
|
36 |
Prime Probing p=3 8 collisions
|
|
|
37 |
Quadratic Probing 8 collisions
|
|
|
38 |
Double Hashing 9 collisions
|
|
|
39 |
Prime Probing p=7 11 collisions
|
|
|
40 |
Linear Probing 14 collisions
|
|
|
41 |
Prime Probing p=5 21 collisions
|
|
|
42 |
Prime Probing p=11 23 collisions
|
|
|
43 |
|
|
|
44 |
So, in terms of least collisions, Prime Probing p=3 and Quadratic Probing are
|
|
|
45 |
the best, and Prime Probing p=11 is the worst. However, analyzing the
|
|
|
46 |
printouts of where the values were inserted leads me to a different
|
|
|
47 |
conclusion. Based on the printouts, I believe that Quadratic Probing is the
|
|
|
48 |
best because it seems to work very well even when the load gets very high.
|
|
|
49 |
This is also true of Double Hashing. I think the result of Prime Probing p=3
|
|
|
50 |
performing very well is a consequence of the data set used. If many different
|
|
|
51 |
data sets were used, I believe that Quadratic Probing and Double Hashing would
|
|
|
52 |
show up as the best general probing methods (best in the majority of cases).
|
|
|
53 |
|