CS 70

Open Addressing

In this part, you'll implement open addressing for your HashMultiset<T> class template. Open addressing is a collision-resolution technique in hash tables where, if a collision occurs, the algorithm searches for the next available slot in the hash table.

Although this part might be the most challenging of the optional parts, it is also a great opportunity to deepen your understanding of hash tables and collision-resolution strategies. And it actually isn't too bad, especially if you haven't done the other optional parts.

The biggest difference between open addressing and separate chaining (which you used in the main part of the assignment) is that, with open addressing, all elements are stored directly in the array that represents the hash table. There are no linked lists or other secondary data structures. When a collision occurs, the algorithm probes the array to find the next available slot.

Your Task

  1. Copy your code from hashmultiset.hpp and hashmultiset-private.hpp into new files named oahashmultiset.hpp and oahashmultiset-private.hpp, respectively.

  2. Change all the names in the new files, including

    • HashMultiset<T> to OAHashMultiset<T>
    • HASHMULTISET_HPP_INCLUDED to OAHASHMULTISET_HPP_INCLUDED
    • #include "hashmultiset-private.hpp" to #include "oahashmultiset-private.hpp"

  3. Remove std::forward_list<KeyCount> as the element type of the buckets array; instead you'll be storing a KeyCount* array (i.e., an array of pointers to KeyCount objects, so each slot holds a key and its count, or nothing). For clarity, it may be helpful to add a type alias within your OAHashMultiset<T> class template similar to

    using BucketType = KeyCount*;

  4. Update your constructor to initialize the buckets array with nullptr values, indicating that all slots are initially empty.

  5. Likewise, ensure that

    • Your resize logic correctly allocates a new array of KeyCount*s and initializes all slots to nullptr; and
    • Your destructor properly deletes any dynamically allocated KeyCount objects and the buckets array itself.

  6. Implement the insert method using linear probing to find the next available slot when a collision occurs. When inserting an element, if the computed bucket index is already occupied (i.e., not nullptr), you should probe linearly (i.e., check the next index, wrapping around to the beginning of the array if necessary) until you find an empty slot.

  7. Implement the count and contains methods to look up a key in the hash table. This function will also require the use of linear probing to search through the array until either the element is found or an empty slot is encountered (indicating that the element is not present).

  8. Update your rehashing logic to correctly transfer elements from the old buckets array to the new one, using the new hash function and linear probing as needed.

When You're Done

Don't forget to add some details about what you did to Fun.md. The sample solution doesn't include open addressing, so before you submit, comment out any OAHashMultiset tests in hashmultiset-test.cpp (our tests of your tests run them against the sample solution).

(When logged in, completion status appears here.)