For your project, you will initially start with a vector linked lists V initialized to being empty. Note that in V, each element points to a linked list. Next, you process each string x, by adding the string x in the linked list pointed by V[h(x)]. For example, if x is David Joe, then the string David Joe is added to the linked list pointed by V[3]. If the hash function gives an index position that is not currently in the vector, then the vector should be expanded to accommodate that position. Initially the size of the vector should be 0.

Your program should be able to handle the following operations.

find(x), determine if the string x is in V. For this purpose, apply the hash function on x, get the index position i and search the linked list associated with V[i]. If the element is not found, search in the linked lists V[i+1], V[i+2], V[i+3], and so on. Note that you should not search the linked lists above V[i].

split(i, p), if the linked lists V[i] has more than p elements, then keep the first p elements in V[i] and move the rest one at a time to positions below i if they have less than p elements, otherwise move them further down. The vector might have to be expanded during this operation.

remove(x), find and delete the string x from V.

insert(x), apply the hash function and insert the string x in V. The vector might have to be expanded during

this operation.

The HashTable class that you will be developing should have the following methods apart from the

methods 1-4 above: empty constructor, destructor, and ostream operator

C++: Using STL library: The input consists of a set of strings on each line. The goal is to perform a hash on each string and store them in a vector of linked lists data structure. You will construct a HashTable class that has the vector of linked lists data structure in it. The hash function h on a string x denoted h(x) results in an integer i which is an index position of the vector of linked lists. For example, if the hash function is h(x) = x[0] A, then for the string Davis Joe, the function value would be 3. Note that in C and C++, chars are identified with their numeric codes and hence numeric operators can be applied on them. The numeric value of character D is D A.