Please answer in C++. Thank you! Given code: #include <iostream> #include <stdli
ID: 3726843 • Letter: P
Question
Please answer in C++. Thank you!
Given code:
#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
#include <ctime>
#include <ratio>
#include <chrono>
#include <math.h>
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 << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
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 < tableSize; hashIndex++){
cout << "Hash Index: " << hashIndex << " : " ;
listArray[hashIndex].IterativePrint();
}
}
};
int main(){
int numElements;
cout << "Enter the number of elements you want to store in the hash table: ";
cin >> numElements;
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
int hashTableSize;
cout << "Enter the size of the hash table: ";
cin >> hashTableSize;
Hashtable hashTable(hashTableSize);
srand(time(NULL));
int array[numElements];
for (int index = 0; index < numElements; 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 table of size 7 that indexes 20 elements overall (as shown in the figure). The maximum size for any linked list in the hash table is 5 (the linked list at 1 | 2 | 3 | 4 | 5 | 6 | Lmin are 35 15 2 38 25 5 34 38 32 47 34 35 15 15 31 11 6 45 48 index 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) = 4/6-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, 1811, 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 metricsExplanation / Answer
here is your modified code : --------------------->>>>>>>>>
#include <iostream>
#include <stdlib.h> //srand, rand
#include <time.h>//clock_t, clock, CLOCKS_PER_SEC
#include <ctime>
#include <ratio>
#include <chrono>
#include <math.h>
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 << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
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;
}
int getLMax(){
int m = 0;
int count;
for(int i = 0;i<tableSize;i++){
count = listArray[i].countList();
if(count > m){
m = count;
}
}
return m;
}
int getLMin(){
int m = listArray[i].countList();
int count;
for(int i = 0;i<tableSize;i++){
count = listArray[i].countList();
if(count < m){
m = count;
}
}
return m;
}
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 < tableSize; hashIndex++){
cout << "Hash Index: " << hashIndex << " : " ;
listArray[hashIndex].IterativePrint();
}
}
};
int main(){
int numElements;
cout << "Enter the number of elements you want to store in the hash table: ";
cin >> numElements;
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
int hashTableSize;
cout << "Enter the size of the hash table: ";
cin >> hashTableSize;
Hashtable hashTable(hashTableSize);
srand(time(NULL));
int array[numElements];
auto start = std::chrono::high_resolution_clock::now();
for (int index = 0; index < numElements; index++){
array[index] = 1 + rand() % maxValue;
hashTable.insert(array[index]);
}
auto finish = std::chrono::high_resolution_clock::now();
std::cout<<"Insertion Time in nanasec = "<< std::chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count() << "ns ";
int lmin = hashTable.getLMin();
int lmax = hashTable.getLMax();
double loadImbalance = (double)(lmax-lmin)/(double)(lmax+lmin);
std::cout<<"Load Imbalance = "<<loadImbalance;
return 0;
}