solution

Introduction

Lab 3

CSC122A
Due 11/12/21, by end of class.

Implement a Hash Table in C++. Use a C++ vector as a list of “Buckets” to store values in, and implement Modulo-Division Hash Function & Linear-Probing.

Implement a constructor for the HashTable class with one parameter named numBuckets.

Inside of the constructor, fill the private vector called buckets with the int value -1. Any bucket with the value of -1 will be considered an unused bucket. One way to accomplish this is to call pushback on the buckets vector, numBuckets amount of times.

Define a hashing function to insert items into the Hash Table. You must implement modular-division hashing.

Implement the private class function hashFunction, so that it takes one integer parameter named value, and returns the integer number of the bucket it should be placed in.

Next, implement a function called insert. insert will attempt to fit its parameter value into the hash table by applying the hash function you created in the previous step. Your insertion function should attempt to add values to the Hash Table with linear-probing.

3.4 5 Points

Next implement a remove function for the Hash Table. remove takes one parameter, an integer bucketNumber to determine where in the Hash Table you should remove a value. To remove the value, visit the bucket specified by the parameter and set the value to unused (-1).

Now design a retrieve class function. The retrieve class function will work similarly to the remove function, however instead of clearing the bucket of its value, the function should return the integer value of the specified bucket.

Finally, extend the printHashTable class function so that we may inspect the contents of the Hash Table. To accomplish this, retrieve the value of each bucket and use cout to print it to the user.

Demonstrate your code in your main function by intializing a HashTable object, inserting and removing values into the HashTable, then call your printHashTable function to show the results. Your code must prompt the user for the amount of buckets the HashTable object should be instantiated with.