For both HashTables, you need to implement the rehashing logic. Rehashing is automatically performed at a load factor of 0.75. Rehashing will re- distribute all existing values to the new buckets. During the rehashing, you should find a new prime number as the new num of buckets to make the load factor < 0.75

Chaining: This is a hash table where the data is stored in a vector of lists. Feel free to use the C++ STL std::vector and std::list classes.

You will also need to keep track of the total number of elements stored in the hash for calculating "size."

Constructor

7 functions

Linear Probing: This is a hash table with a single vector of elements, but it MUST do lazy deletion (a value is marked as deleted but only

physically deleted when a new value is inserted at the same place). This HashTable needs to keep track if a bucket is empty, full, or deleted and your code must use that information when probing and rehashing. You'll need to keep track of the total size of the hash table (excluded those marked "deleted" values). This is doing linear probing: probe(i) = i.

Constructor

7 functions

Test cases:

The main.cpp already has the following test cases. Don't change the

main.cpp. You need to make sure these test cases can run properly.

1. Create a HashTable (initial num of buckets: 101)

2. Insert 100,000 records (rehash will automatically take place according

to the load factor)

3. Search for key 97

4. Erase key 97

5. Search for key 10000

6. Clear the hash table

The main.cpp will also print the time taken by operation 2,3,4.

In the project directory, create a file called "output.txt" and put the output of

main.cpp to this file when submitting.