We want to keep a hash table that stores the students in our section. Each student has two info

field: student id and name. Student id is going to be used as the key.

Implement a hash table class that provides the following public methods.

$$ insert: this takes a student object $($id$-$name pair$)$ and store the object in the hash table

using the id as the key. This function should not allow any duplicate keys $($i$.$e$.,$ no two

students with the same id$)$ in the table.

$$ retrieve: this takes a key $($id$)$ and retrieves the value $($name$)$ associated with the key if it

is found.

Hence, only insert and retrieve operations can be used with objects of this hash table class. The

default constructor and destructor have been provided for your convenience.

Use Open Addressing $($with linear probing$)$ resolution method. Use the hash function h$($key$)=$

key $\%$ TableSize. Here the key is student ID$.$

To implement you can use the following hashTable.h as a starter. To test your solution write

your own driver code in main.cpp$.$ Do not submit your main.cpp$.*$For your convenience, a

sample main.cpp is enclosed in the Appendix.

$//$ starter hashTable.h file

struct Student $\{$

int id; $//$ this is the key

string name;

$\}$;

class hashTable $\{$

public:

hashTable$($int capacity$=203)\{$

size$=0$;

TableSize$=$capacity;

if $($TableSize $<=0)$

TableSize $=203$;

list$=$ new Student$[$TableSize$]$;

for $($int i$=0$; i$<$ TableSize;i$++)$

list$[$i$].$id$=$ SentinelID; $//$ initially all of the entries empty

$\}$

bool insert$($Student &st$)\{$

$2$

$//$ returns true if the st is inserted, returns false if the st is

not inserted $($e$.$g$.,$ an object with the same key already exists or

the table is full$)$

$//$ the hash function is st$.$id $\%$ TableSize;

$//$ write your code here

$\}$

bool retrieve$($int id$,$ string &name$)\{$

$//$ the function returns true and the name $($if the id appears in the

table$).$ Otherwise, the function returns false

$//$ write your code here

$\}$

~hashTable$()\{$

delete $[]$ list;

$\}$

private:

int TableSize;

int size;

int SentinelID$=-1$; $//$ to understand whether the entry is empty

Student $*$list;

$\}$

Appendix: Sample main.cpp

#include

#include "hashTable.h

using namespace std;

$//$ The driver code for the class hashTable

int main$()$

$\{$

hashTable myHT$(13)$; $//$ small table of size $13$ is enough to test

Student st;

st$.$id $=111111$;

st$.$id $=$Ali$$;

myHT$.$insert$($st$)$;

st$.$id $=222222$;

st$.$id $=$Aesha$$;

myHT$.$insert$($st$)$;

st$.$id $=222222$;

st$.$id $=$Hasan$$;

if $($myHT$.$insert$($st$))//$ to test the duplicate insertion

$3$

cout $<<$ "Student with id$="<<$ st$.$id $<<"$ and with name$="<<$

st$.$name $<<"$ is inserted into the table" $<<$ endl;

else

cout $<<$ "Unable to insert Student:" $<<$ st$.$id $<<$ endl;

int queryid $=111111$;

string name;

if $($myHT$.$retrieve$($queryid$,$ name$))$

cout $<<$ "Student $"<<$ queryid $<<"$ has the name$="<<$ name $<<$ endl;

else

cout $<<$ "Student $"<<$ queryid $<<"$ is not in the table" $<<$ endl;

int queryid $=333333$;

string name;

if $($myHT$.$retrieve$($queryid$,$ name$))$

cout $<<$ "Student $"<<$ queryid $<<"$ has the name$="<<$ name $<<$ endl;

else

cout $<<$ "Student $"<<$ queryid $<<"$ is not in the table" $<<$ endl;

return $0$;$\}$