HINT -- Consider infusing auto-rehashing into the appropriate core algorithm(s) at the appropriate place(s).
Algorithm for Method 'put(key, value)'
This method receives a key and value and should insert the value into the hash table at the key (so that later the value can be looked up by the key).
- Receive key and value to add to hash table
- Use a hash function to compute a hashCode (integer) from the key
- Convert the hashCode to a valid bucket index
- Get the bucket at the bucket index
- Search for the matching association in the "bucket" using the key
- If found, replace the association's old value with the new value, otherwise add a new association (with new key and value) to the bucket
- Increment hash table size
- Return the association's old value or null if no match was found (this step may vary -- see ADT's method description)
Algorithm for Method 'get(key)'
This method receives a key and searches for the associated value. If found, it returns the associated value, otherwise it returns null.
- Receive key used to get the value
- Using the same hash function used for the "put", we compute a hashCode (integer) from the key
- Convert the hashCode to a valid bucket index
- Get the bucket at the index position
- Search for the matching association in the "bucket" using the key
- If an association was found, return the association's value, otherwise return null (verify no-match return with ADT)
Algorithm for Method 'removeKey(key)'
This method receives a key to remove from the hash table.
- Receive key to remove
- Use a hash function to compute a hashCode (integer) from the key
- Convert the hashCode to a valid bucket index
- Get the bucket at the bucket index
- Search for the matching association in the "bucket" using the key
- If a matching association is not found, throw exception or return null, etc (verify handling of no-match with ADT)
- Decrement hash table size
- Return the matching association's old value (verify return type with ADT)
Algorithm Gap
The core algorithms have a gap: How do we search for a key in a bucket?