CS 70

Phase 5: Rehashing

To meet our complexity guarantees when people don't know the size of their hash table ahead of time, we need to be able to rehash the hash table, creating a new, different-sized, underlying array of buckets and moving our items into that array.

Handy reference material:

Let's Go!

  • RHS Cow speaking

    There are some good tips in the Hints and Tips section; check them out before you start!

Following our usual development process, implement the following functions:

  • loadFactor
  • maxLoadFactor
  • rehash
  • reallocations

Also: Adjust the code for insert so that if an insert would cause the load factor to exceed the maximum, the rehash function is called automatically.

Planning Image

Add a planning image, Phase_5.jpg, to the Planning folder.

Hints and Tips

Writing loadFactor

This function should return the current load factor of the table (i.e., the number of keys divided by the number of buckets).

The load factor of an empty table should be 0.

Careful! The load factor is a double value but dividing one integer by another will result in an integer value!

Writing rehash

Probably the easiest way to write rehash is to

  • Create a new (empty) HashSet with the desired properties.
  • Go through each bucket in the original hash set, taking the data out of the original hash set and inserting the data into the new hash set using a special insertion function that doesn't check to see if the item is already in the new hash set (since we know it won't be).
  • Finish up by swapping the new hash set and the old one.
  • The old HashSet will get cleaned up automatically when the variable goes away.

Testing

Because you can explicitly call rehash and explicitly set the maximum load factor, either in the constructor or via maxLoadFactor, you can write tests that will work on any correct HashSet implementation.

(When logged in, completion status appears here.)