#include

#include //srand, rand

#include //clock_t, clock, CLOCKS_PER_SEC

#include

#include

#include

#include

using namespace std;

// implementing hash tables as an array of linked lists

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class List{

private:

Node *headPtr;

public:

List(){

headPtr = new Node();

headPtr->setNextNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void insert(int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

while (currentNodePtr != 0){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

prevNodePtr->setNextNodePtr(newNodePtr);

}

void insertAtIndex(int insertIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

prevNodePtr->setNextNodePtr(newNodePtr);

}

int read(int readIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == readIndex)

return currentNodePtr->getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

bool deleteElement(int deleteData){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

while (currentNodePtr != 0){

if (currentNodePtr->getData() == deleteData){

nextNodePtr = currentNodePtr->getNextNodePtr();

prevNodePtr->setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

int countList(){

Node* currentNodePtr = headPtr->getNextNodePtr();

int numElements = 0;

while (currentNodePtr != 0){

numElements++;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return numElements;

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout getData()

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout

}

bool containsElement(int searchData){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

if (currentNodePtr->getData() == searchData)

return true;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

};

class Hashtable{

private:

List* listArray;

int tableSize;

public:

Hashtable(int size){

tableSize = size;

listArray = new List[size];

}

int getTableSize(){

return tableSize;

}

void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

void deleteElement(int data){

int hashIndex = data % tableSize;

while (listArray[hashIndex].deleteElement(data));

}

bool hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

void printHashTable(){

for (int hashIndex = 0; hashIndex

cout

listArray[hashIndex].IterativePrint();

}

}

};

int main(){

int numElements;

cout

cin >> numElements;

int maxValue;

cout

cin >> maxValue;

int hashTableSize;

cout

cin >> hashTableSize;

Hashtable hashTable(hashTableSize);

srand(time(NULL));

int array[numElements];

for (int index = 0; index

array[index] = 1 + rand() % maxValue;

hashTable.insert(array[index]);

}

return 0;

}

You are given the code to construct a hash table of size 'm' for an array of 'n'integers. The hash table is an array of singly linked lists. Your task in this quiz is to extend the code in the main function as well as the code in the Hashtable class to determine the following for different values of the hash table size (m): (1) average time per insertion (measured in nanoseconds) in the hash table (2) load imbalance index, a measure of the efficiency in using the memory allocated for the hash table Explanation of Load Imbalance Index: The "Load Imbalance Index" for a hash table is calculated as the ratio (Lmax-Lmin) / (Lmax + Lmin), where Lmax and Lmin are respectively the maximum and minimum lengths of the linked lists in the hash table. For example, consider the structure of a hash 2 4 35 15 2 38 25 5 34 35 15 38 32 47 34 table of size 7 that indexes 20 elements overall (as shown in the figure) 31 11 45 15 The maximum size for any linked list in the hash table is 5 (the linked list at 48index 6) and the minimum size for any linked in the hash table is 1 (the 20 linked list at index 2). Hence, the Load Imbalance Index for the hash table in the example is (5-1) / (5 + 1)-46-067 For your quiz, the number of integers (n) to be inserted is 100000 and the maximum value for an integer is 50000. The array of integers to be inserted is randomly generated, as given in the code. As we discussed in class, the hash table size (m) is a prime integer The prime integers (m) to be used for this quiz are: 11, 29,47.71. 173, 281, 409, 541, 659, 809,941, 1069, 1223,1373, 1511, 1657, 181. 1987. 2129 Tabulate the results for hash table size (m) vs. (average time per insertion (in nanoseconds), load imbalance index) Plot the results in Excel with the hash table size (m) in the X-axis and the average insertion time, load imbalance Index in the Y-axis. You could plot them separately (i.e, hash table size vs. average time per insertion and hash table size vs. load imbalance index in separate charts) or together with primary and secondary Y-axes (i.e., the average time per insertion as the primary Y-axis and the load balance index as the secondary Y-axis in the same Excel chart). Analyze the results to infer about the impact of the hash table size on the average time per insertion and the load imbalance index and the tradeoff between the two metrics ubn (1) The entire code with the main function and the hash table class enhanced to determine the average time per insertion and load imbalance index. Your code accept the hash table size as input or could be automated to run for the given set of prime integers as the hash table sizes. (2) Screenshots of your execution for any four of the prime integers from the above list. (3) Table presenting the results for the hash table size (m) vs. average time per insertion (in nano seconds) and load imbalance index for all the given values of the hash table size. 4) Excel chart(s) for the data in (3) and your inference about the impact of the hash table size (m) on the average time per insertion and load imbalance index. Is there any tradeoff between the average time per insertion and load imbalance index? Explain