Skip to content

Hashing Homework

In this assignment, you will implement a hash table using closed hashing with linear probing.

Remember, closed hashing (confusingly also called open addressing) means that the table itself contains the values, so only one item is stored in each slot.

In this case, if a collision occurs, we will use linear probing to find the next available slot.

You will also implement tombstone deletion. This means that when an item is deleted, it is not removed from the table, but marked as deleted. This allows us to keep the probing sequence intact. When new items are added, they will replace the tombstones.

Part 1 - Understanding Insertion

Download the following two files:

Take a few minutes to read over the provided put method before answering the Part 1 questions in Gradescope.

Part 2 - Implementation

Before diving in, scan through the code to see what state, methods, and helper classes are available.

Pay attention specifically to:

  • indexFor() - you should call this method to get the index that a key should be placed in the table. Every object has a .hashCode() method you can call. This code should be passed to indexFor to get the index. Example:
String thisIsMyKey = "apple";
int index = indexFor(thisIsMyKey.hashCode(), table.length);

  • debugString() - you can call this method to get a string representation of the table. This is useful for debugging.

  • Item - this class is used to store the key-value pairs in the table. It has a deleted instance variable that indicates whether the item is a tombstone. You should use this field to mark items as deleted.

After you have read through the code, complete the following tasks in the recommended order:

  • Implement the findKey helper method. Use open addressing with linear probing to resolve collisions. If the probe encounters a previously deleted item, continue on to the next slot as described in the textbook. This helper method should be used by put, get, and remove.

  • Implement get. If the key can't be found, return null.

  • Implement remove. If the key can't be found, return null. Don't delete by nulling out the cell, as this action would break the probing sequence. Use the attributes of Item instead.

  • Implement resize. Double the table size and migrate all the old, non-deleted items to the new table. You can't just put the old items in the same cells, however, because an item's position depends on the table size.

  • Implement the iterator.

  • Implement loadFactor.

Note: While we are not requiring you to submit unit tests for this assignment, you should test your implementation as you work. There will be a grade penalty for submissions beyond 10.

Part 3 - Benchmarking

Download the following two files and add them to your project:

The DictionaryBenchmark.java evaluates the efficiency of various dictionary implementations by timing insertion, search, and removal operations. The dictionaries being evaluated are the same sort of word indexes we explored in the previous homework assignment.

Run the benchmarking code on the following three files and save the output.

  • alice.txt - Alice's Adventures in Wonderland by Lewis Carroll (3192 distinct words).
  • moby_dick.txt - Moby Dick by Herman Melville. (19959 distinct words).
  • fake_book.txt - A fake book with many "words". (99313 distinct words).

Look over your results and answer the Part 3 questions in Gradescope.

Grading

Part 1 Answers 2 points
Part 2 Autograder Results 6 points
Part 3 Answers 2 points