CS 70

Open Addressing

In this part, you'll implement open addressing for your HashSet<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 hashset.hpp and hashset-private.hpp into new files named oahashset.hpp and oahashset-private.hpp, respectively.

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

    • HashSet<T> to OAHashSet<T>
    • HASHSET_HPP_INCLUDED to OAHASHSET_HPP_INCLUDED
    • #include "hashset-private.hpp" to #include "oahashset-private.hpp"

  3. Remove std::forward_list<T> as the element type of the buckets array; instead you'll be storing a T* array (i.e., an array of pointers to T objects). For clarity, it may be helpful to add a type alias within your OAHashSet<T> class template similar to

    using BucketType = T*;

  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 T*s and initializes all slots to nullptr; and
    • Your destructor properly deletes any dynamically allocated T 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 exists method to check for the presence of an element 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 includes an open-addressing implementation, so you can leave your tests in hashset-test.cpp enabled if you'd like rather than commenting them out.

(When logged in, completion status appears here.)