16 - Hash Table

Introduction

Files

Download the following files:

• HashTable.java

Instructions

Before diving in, scan through the code to see what state, methods, and helper classes are available. Then complete these tasks:

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

• 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. Automatically resize the table if the load factor exceeds MAX_LOAD.

Lab Submission

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