irected Lab Work

A hash table class with linear collision resolution has already been implemented in the

HashedDictionaryOpenAddressingLinear class. You will implement three new classes

HashedDictionaryOpenAddressingLinearInstrumented $,$

HashedDictionaryOpenAddressingDoubleInstrumented $,$ and

HashedDictionaryOpenAddressingPerfectInstrumented based on that class. They will allow you to

gather statistics about the number of probes made to insert values. The HashPerformance class will generate

random arrays of keys, insert the keys in the various kinds of hash tables, and then display the averages.

Implementing Double Hashing

Step $1.$ If you have not done so$,$ look at the implementation of a hash table with linear probing in

HashedDictionaryOpenAddressingLinear.java $.$ Look at the code in CheckSearchHashTable.java $.$

Compile the classes CheckSearchHashTable and HashedDictionaryOpenAddressingLinear $.$ Run the

main$()$ method in CheckSearchHashTable $.$

Checkpoint: The program will ask you for the number of trials, the number of data values, and a seed. Enter $1,$

$1000,$ and $123,$ respectively. An array of $1000$ random values between $0$ and $1000$ should be generated. The

first $500$ of those values will be inserted into a hash table. The code will check that searches work correctly.

The first $250$ values in the array will then be removed from the hash table. Again searches will be checked.

Finally, the last $500$ values in the array will be added into the hash table. Again searches will be checked.

Verify that the code passed each of the three tests.

The first goal is to create the class for double hashing and verify that it works.

Step $2.$ Copy HashedDictionaryOpenAddressingLinear.java into a new file

HashedDictionaryOpenAddressingDoubleInstrumented.java $.$

Step $3.$ Create a new private method getSecondHashIndex$($Object key$),$ which computes a second

hash function. Refer to the formula created in the pre$-$lab exercises.

Step $4.$ Refer to the pre$-$lab exercises and modify the locate$()$ and probe$()$ methods to use double

hashing instead of linear hashing.

Step $5.$ Change the code in CheckSearchHashTable so that it creates a new object of type

HashedDictionaryOpenAddressingDoubleInstrumented $.$

Run the main method in CheckSearchHashTable $.$

Lab $17$ Hash Table Implementation$240$

Checkpoint: Use $1,1000,$ and $123$ for the input values.

Verify that the code passed each of the three tests. If not, debug the code and retest.

The next goal is to create the class for perfect hashing and verify that it works.

Implementing Perfect Hashing

Step $6.$ Copy HashedDictionaryOpenAddressingLinear.java into a new file

HashedDictionaryOpenAddressingPerfectInstrumented.java $.$

Step $7.$ Create a new private method getHashGenerator$($Object key$)$ which will create and return a

random number generator that will be $$used to generate the sequence of probes. Refer to your answer from the

pre$-$lab exercise.

Step $8.$ Again, refer to the pre$-$lab exercises and modify the locate$()$ and probe$()$ methods to use

perfect hashing instead of linear hashing. $($Remember to change the first argument to be a random number

generator instead of an integer.$)$

Step $9.$ Find all places where the locate$()$ and probe$()$ methods are called and change it so that

getHashGenerator is called invoked instead of getHashIndex $.$ Once you are finished, there should no

longer be any calls to getHashIndex $.$ Remove the getHashIndex method.

Step $10.$ Change the code in CheckSearchHashTable so that it creates a new object of type

HashedDictionaryOpenAddressingPerfectInstrumented $.$

Run the main method in CheckSearchHashTable $.$

Checkpoint: Use $1,1000,$ and $123$ for the input values.

Verify that the code still passes each of the three tests. If not, debug the code and retest.

Adding Statistics

Step $11.$ Copy HashedDictionaryOpenAddressingLinear.java into a new file

HashedDictionaryOpenAddressingLinearInstrumented.java $.$

Step $12.$ Refer to the pre$-$lab exercises and add in code to the locate$()$ and probe$()$ methods that will

count the number of probes.

Step $13.$ Change the code in CheckSearchHashTable so that it creates a new object of type

HashedDictionaryOpenAddressingLinearInstrumented $.$

Run the main method in CheckSearchHashTable $.$

Checkpoint: Use $1,1000,$ and $123$ for the input values.

Verify that the code still passes each of the three tests. If not, debug the code and retest.

Step $14.$ Make similar changes in HashedDictionaryOpenAddressingDoubleInstrumented and

HashedDictionaryOpenAddressingPerfectInstrumented $.$

Step $15.$ Change the code in CheckSearchHashTable so that it creates a new object of type

HashedDictionaryOpenAddressingDoubleInstrumented $.$ Run the main$()$ method in

CheckSearchHashTable $.$

Checkpoint: Use $1,1000,$ and $123$ for the input values.