Hashing Lab

CPE 103 Hashing Lab

Step 1 gives you some test data for this activity, as well as practice with Quadratic Probing.

1. Hash the following keys into a table of size 21 using a hash function of h(x) = x mod 21. Resolve collisions with quadratic probing.
7, 22, 44, 43, 27, 89, 30, 64, 85

Draw a diagram of the completed table. Check your results with the instructor.

For this activity we are going to study Weiss's implementation of a hashtable.

The following files are needed.

You may remove the "package DataStructures;" statement at the top of each file.

2. Make sure it compiles and executes correctly.

3. Add a new accessor method, public HashEntry[] getTable() that returns a copy of the underlying array for us to examine.

4. Write a JUnit test to demonstrate that the program is working correctly. That is, we want to verify that items inserted into the hash table are actually placed in the correct spot in the array according to the Quadratic Probing technique.
Create a JUnit test that inserts the numbers from the exercise above into Weiss's table. Then invoke the getTable() method to obtain the completed table. Write nine assert statements to confirm that each number was placed in the proper location in the table.

5. Convert QuadraticProbingHashTable.java to meet the class coding standards (except the main() method).

Place your names in separate @author tags in the class header.
Always use braces, even if the block has a only single statement.
Use while statements for conditional loops, not for.
Convert ternary expressions to if statements.
Move pre and postfix operations within an expression to separate statements.
Use the class coding standard for constants.

6. Add a comment to every executable statement that explains what it does, in terms of the abstraction,
not in terms of Java operations.

For example,
for( int i = 0; i < key.length( ); i++ )

Don't say "Loops from zero to key length",
Say "Examine every letter in the key."

The goal is that you should thoroughly understand how the implementation operates and accomplishes its tasks.

7. Run your JUnit tests and verify they still pass. If not, correct the defects.

8. Submit to Web-CAT a zip file containing the source code for all the classes, including the unit tests. Your submission should pass the instructor's reference tests. There is nothing else to submit for this lab.