C++:
Implement project4.cpp file, which creates a HashTable object with parameter 10007 for the constructor. The constructor of HashTable uses this prime number to build an internal SLL object array. Each element of the array is an SLL object. Of course, you can choose a different array size, but make sure the size is a prime number.
#include #include #include "hashTable.h" #include #include #include
using namespace std;
int main(int argc, char* argv[]){
// implement this missing part // make the array size inside the hash table is 10007 }
OUTPUT:
$ ./project4 40000-idr The Number of Valid Insertation :26214
The Number of Valid Deletion :2795
The Number of Valid Retrieval :2867
Item numbers in the list :23419 Time elaspsed :0.102787
hashtable.h (given)
#include #include "SLL.h" #include #include using namespace std;
template class HashTable { int tableSize; // table size SLL* table; public: // default constructor, which uses default table size 3 HashTable() { tableSize = 3; table = new SLL[tableSize]; } // constructor, which use size as the table size HashTable(int size) { tableSize = size; table = new SLL[tableSize]; } // search item in the table // if found, return true; otherwise, return false bool find(V item){ long hashVal = 0; long compressVal = 0; for(int i=0; i<=item.length()-1; i++) { int power = item.length()-1-i; hashVal = hashVal + ((int)(item.at(i)))*(pow(31, power)); } compressVal = abs((hashVal)%(10007)); SLL* temp = &table[compressVal]; if(temp->search(item) != NULL){ return true; } else{ return false; } } // insert (item1, item2) to the table // use item1 as the key // if inserted, return true // otherwise, return false bool insert(V item1, V item2) { long hashVal=0; long compressVal=0; for(int i=0; i<=item1.length() - 1; i++){ int power = item1.length() - 1 - i; hashVal = hashVal + ((int)(item1.at(i))) * (pow(31, power)); } compressVal = abs((hashVal)%(10007)); SLL* temp1 = &table[compressVal]; if(temp1->search(item1) != NULL){ return false; } SLL* temp2 = &table[compressVal]; temp2->insert(item1, item2); SLL* temp3 = &table[compressVal]; if(temp3->search(item1) != NULL){ return true; } else{ return false; } } // delete the pair whose key value is item // if deleted, return true // otherwise, return false bool erase(V item) { long hashVal=0; long compressVal=0; for(int i=0; i<= item.length() - 1; i++) { int power = item.length() -1 - i; hashVal = hashVal + ((int)(item.at(i)))*(pow(31, power)); } compressVal = abs((hashVal)%(10007)); SLL* temp1 = &table[compressVal]; if(temp1->remove(item)) { return true; } else { return false; } } // return the total number of nodes in the hash table int getSize() { int nodeCount = 0; for(int i=0; i<=tableSize-1; i++) { SLL* temp = &table[i]; nodeCount = nodeCount + temp->getSize(); } return nodeCount; } };