Skip to content

Lab: Hashing

In this lab, 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.

Starter Code

Instructions

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 tombstone instance variable that indicates whether the item has been deleted. 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 put. The findKey helper method can be used to determine if the key is already in the table. If so, the value should be replaced. If not, a new entry must be added to the table.

    • If the table is full, call resize to increase the size of the table.

  • 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 methods 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.

Submitting

Test each step as you complete it. Once you are confident your implementation is correct, submit HashTable.java through Gradescope.