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:
Let's Go!
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:
loadFactormaxLoadFactorrehashreallocations
Also: Adjust the code for insert so that, after it adds a new key, if the load factor is now above the maximum, it calls rehash. (So right after an insert that adds a new key, the load factor is at most the maximum.)
And now that your table can grow, 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.)
Planning Image
Add a planning image, Phase_6.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).
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 1,000,000 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) 😉
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) local
HashMultisetwith 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
KeyCountin 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).swapexchanges 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.
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.)