IIn this project, you will implement an important data structure called the hash table. This project requires you to implement a hash table to fulfill the functionality provided by project $2$ and project $3.$ You will first implement a singly linked list class SLL in SLL$.$h file, then implement HashTable class that is in hashTable.h file. Lastly, implement project$4.$cpp file. Please read this handout before coding. A node.h file is provided. Do NOT change the node.h file. The end of this handout has important guidelines to be used in testing.

Your Implementation:

This project includes three parts:

$1)$ Implement the unfinished methods of the SLL class in the SLL$.$h file, do NOT change anything in the node.h file. SLL must be class TEMPLATE. Use

placeholder wherever you do not want to use fixed data type.

$2)$ Implement HashTable class, which is class template, in hashTable.h file. The default constructor uses $3$ as the table size. The constructor with parameter uses the parameter value as the table size. Do not hard$-$code array size in your constructors. Let the user decide what array size will be$.$

$3)$Implement project$4.$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.

There are multiple input files included in the zip file. Please note that we have new files whose data set sizes are larger than the files of the previous projects.

To compile the source code, you can type the following command:

g$++-$Wall project$4.$cpp $$o project$4$

Hints:

Because the SSN values are evenly distributed in the input files, the hash

function in your implementation can be as simple as h$($k$)=$ k mod m$,$ where m is the table size.

Your program should work with all the provided input files, including the

$750000-$idr.

The executable file will be project$4.$ If your hash table implementation is right, when we execute file project$4,$ the result looks like the following contents:

$./$project$440000-$idr

The Number of Valid Insertion: $26214$

The Number of Valid Deletion: $2795$

The Number of Valid Retrieval: $2867$

Item numbers in the list: $23419$

Time elapsed: $0\mathrm{.}102787$

$./$project$460000-$idr

The Number of Valid Insertion: $39228$

The Number of Valid Deletion: $4262$

The Number of Valid Retrieval: $4386$

Item numbers in the list: $34966$

Time elapsed: $0\mathrm{.}150879$

$./$project$4250000-$idr

The Number of Valid Insertion: $156536$

The Number of Valid Deletion: $28338$

The Number of Valid Retrieval: $18613$

Item numbers in the list: $128198$

Time elapsed: $0\mathrm{.}692797$

$./$project$4500000-$idr

The Number of Valid Insertion: $312656$

The Number of Valid Deletion: $56010$

The Number of Valid Retrieval: $37360$

Item numbers in the list: $256646$

Time elapsed: $1\mathrm{.}88009$

SLL$.$h

#include iostream

#include "node.h$"$

using namespace std;

template

class SLL $\{$

Node $*$ headPtr;

int size;

public:

$//$ default constructor

SLL$()\{$

$//$implement this method

$\}$

$//$ destructor

~SLL$()\{$

$//$ implement this method

$\}$

Node$*$ getHeadPtr$()\{$

return headPtr;

$\}$

$//$ insert $($item$1,$ item$2)$ to the list

void insert$($U item$1,$ U item$2)\{$

$//$implement this method

$\}$

$//$ if find the item$1$ value, return the pointer to the node

$//$ otherwise, return nullptr

Node$*$ search$($U item$1)\{$

$//$implement this method

$\}$

$//$ remove the node with key value: item$1$

bool remove$($U item$1)\{$

$//$implement this method

$\}$

int getSize$()\{$

return size;

$\}$

$//$ display the SSN values of each node in the linked list

void display$()\{$

Node$*$ temp;

temp $=$ headPtr;

while $($temp$!=$ nullptr$)\{$

cout $$ temp$->$SSN $$ endl;

temp $=$ temp$->$next;

$\}$

$\}$

$\}$;

hashTable.h

#include iostream

#include $"$SLL$.$h$"$

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$)\{$

$//$ implement this method

$\}$

$//$ search item in the table

$//$ if found, return true; otherwise, return false

bool find$($V item$)\{$

$//$ implement this method

$\}$

$//$ insert $($item$1,$ item$2)$ to the table

$//$ use item$1$ as the key

$//$ if inserted, return true

$//$ otherwise, return false

bool insert$($V item$1,$ V item$2)\{$

$//$implement this method

$\}$

$//$ delete the pair whose key value is item

$//$ if deleted, return true

$//$ otherwise, return false

bool erase$($V item$)\{$

$//$ implement this method

$\}$

$//$ return the total number of nodes in the hash table

int getSize$()\{$

$//$ implement this method

$\}$

$\}$;

Node.h

#include iostream

using namespace std;

template

struct Node$\{$

T SSN;

T name;

Node$*$ next;

$\}$;

project$4.$cpp

#include iostream

#include fstream

#include "hashTable.h$"$

#include string

#include time.h

#include ctime

using namespace std;

int main$($int argc, char$*$ argv$[])\{$

$//$ implement this missing part

$//$ make the array size inside the hash table is $10007$

$\}$