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.