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.
Test each step as you complete it. Once you are confident your
implementation is correct, submit HashTable.java through Gradescope.