Complete the four functions in the following program to construct two hash tables using C++ vectors. One hash table uses linear probing, and the other hash table uses quadratic probing. In your program, count the number of collisions required in a sequence of 20 random insertions of integers between 0 and 100. Use a table size of 31. Output must display the integers inserted and the hash tables after insertions.

#include

#include

1

2

3

4

5

6

7

using namespace std;

const int TABLESIZE = 31;

l/hash function defined as

Here is the code in text:

#include

#include

using namespace std;

const int TABLESIZE = 31;

//hash function defined as modulo operator

//receive an item key and return bucket index

template

int hfun(T key)

{

//your code here

}

//insert an item in the hash table

//Collision resolution by Linear Probing

// retuns the number of collisions when inserting the key

template

int hashInsertLprobe(vector& h, T key)

{

//your code here

}

template

void printHashTable(vectorh)

{

//your code here

}

//hash insert, quadratic probing

// retuns the number of collisions when inserting the key

template

int hashInsertQ(vector& h, T key)

{

//your code here

}

int main()

{

vector hTableL(TABLESIZE, -1); //initialize the hash table (all cells set to -1)

vector hTableq(TABLESIZE, -1);

int collisionCountL = 0;

int collisionCountQ = 0;

int x;

cout

for (int i = 0; i

{

x = rand() % 101; //random integer between 0 and 100

cout

//insret key into the hash and increment collisions

collisionCountL += hashInsertLprobe(hTableL, x);

collisionCountQ += hashInsertQ(hTableq, x);

}

cout

cout

printHashTable(hTableL);

cout

cout

printHashTable(hTableq);

system(\\\"pause\\\");

return 0;

}