The goal is to implement a hash table in C/C++ using open addressing.

Part A : Hash Table Implementation

• Create a hash table struct/class that uses open addressing. Do not use any library data structures for implementing your hash tables.
• Use the multiplication method for generating your hash function and linear probing to resolve collisions in open addressing.

Part B : Populating the Hash Table

After constructing the hash table, do the following:

• Generate a random number within the range (0 to 100000).
• Map the generated number to a random integer and insert it into your hash table.
• During insertion, measure the number of times that you have to reprobe the hash table before inserting the value.

Repeat the above operations until your hash table has a load factor of 50% and 90%. Find the average number of reprobes for inserting a random number into the hash table in both cases.

Part C : Search operation

• Generate a random number within the range (0 to 100000). Do not seed your random number generator.
• Search for the number in your hash table.
• Measure the number of times that you have to reprobe the hash table when it is 50% and 90% full to find the corresponding value.

Repeat the above operations 10000 times and measure the average number of reprobes that have to be performed for a search operation in your hash table.

Implementation Details

Design your hash table in such a way that the number of reprobes is very small.

If the number of reprobes is large, then modify your hash table design in such a way that the issue is resolved.