Phase 6: 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:

• Specifications for HashMultiset<T>

Let's Go!

Following our usual development process, you will implement the following functions:

• loadFactor
• maxLoadFactor
• rehash
• reallocations

You will also be updating the insert function and setting reasonable defaults for some parameters affecting your table's size and load factor.

Hints and Tips

Writing loadFactor

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

Note that in this definition, the numerator in the division is the number of keys, not the size of the HashMultiset! The specifications say that size returns the total count, but a specific key having a count of 1000000 versus a count of 1 has no impact on the load factor, because either way the table only contains one KeyCount item for that key.

If you get stuck on this part, remember that there is no cost to adding more private member variables (as long as you remember to keep them updated) 😉

Keep in mind that the load factor is a double value but dividing one integer by another will result in an integer value!

The load factor of an empty table should be 0.

Writing rehash

Probably the easiest way to write rehash is to

• Create a new (empty) local HashMultiset with the desired properties: the same maximum load factor, and enough buckets to bring the load factor down to at most half the maximum. (Exactly how many is your choice.)
• Go through each bucket in the original hash table, taking each KeyCount in the bucket and directly inserting it into the new table using a special private helper function. If you went through the Helpful Hints in the previous parts, perhaps you already have such a helper function!
• Before you swap, make sure the new table has the right counters: one more reallocation than the old one, and the same size (unless your helper already adds up the counts as it inserts). swap exchanges every data member, counters included.
• Finish up by swapping the new hash set and the old one.
• After the swap, your local variable holds the old buckets, and they're cleaned up automatically when it goes out of scope at the end of rehash.

Modify insert

Adjust the code for insert to check the load factor after adding a new key. If the load factor is greater than the maximum allowed (from DEFAULT_MAXIMUM_LOAD_FACTOR in hashmultiset.hpp), insert then calls rehash to resize the hash table. (Thus the load factor after adding a new key is at most the maximum value.)

Update Placeholder Values

Now that your table can grow to handle more data, replace the placeholder values of DEFAULT_NUM_BUCKETS and DEFAULT_MAX_LOAD_FACTOR in hashmultiset.hpp (the ones marked FIXME) with sensible ones. (For separate chaining, a maximum load factor somewhere between 0.5 and 2 is typical.)

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 HashMultiset implementation.

One thing you can always test: right after inserting a new key, loadFactor() is at most the maximum load factor. (Not necessarily after re-inserting a key that's already there, if you've lowered the maximum with maxLoadFactor since the last rehash.)

(When logged in, completion status appears here.)

Previous Page Next Page