Please write the program in C++. Hash Table with Chaining Description In this as
ID: 3863820 • Letter: P
Question
Please write the program in C++.
Hash Table with Chaining Description In this assignment you are requested to implement a hash table that handles collisions by chaining. You have to use linked lists, either from the Standard Template Library (STL) recommended) or by implementing your own. For usage of STL, refer for instance to http://www.cppreference.com/wiki. You need to implement the insert, search and delete operations. The keys are integers (C++ int type) and you can assume that all keys are non-negative. The first number in the input will be the size m of the chained hash table. You will use the simple hash function h(k) k mod m Then lines will follow starting with i S 'd', o or e The details are as follows Use the hash function h(k) k mod m i key): Insert (key) into the table. For example, "i2" implies "Insert key 2 into the table." For collisions, insert the colliding key at the beginning of the linked list. You just need to insert the key and don't have to output anything in this case d(key): delete (key) from the table. For example, d2 implies "Delete key 2 from the table." If there are multiple elements of the same key value, delete the element of the key value that appears the earliest in the list. If the delete was successful, you have to output (key) DELETED If not (since there was no element with the key value), output (key) DELETE FAILED s(key): search (key) in the table. If there is an element with the key value, then you have to output (key) FOUND ATi,j; where i is the hash table index and j is the linked list index. If there are multiple elements with the same key value, choose the first one appearing in the linked list. If you couldn't find the key, then output (key) NOT FOUND o: output the table. Output the entire hash table. Each line should begin with the slot hash table index followed by key values in the linked list. For example, if m 3 and we inserted 3, 6, and 1 into an empty table in this order, then you should output 1:1- e: finish your program.Explanation / Answer
c++ code:
#include <iostream>
#include <list>
using namespace std;
class HashTable{ // hashTable class
private:
list<int> *hashTable;
public:
HashTable(){ //initialize hastable to null on creation
hashTable=NULL;
};
~HashTable(){ // deleting hashtable on destruction
if(hashTable!=NULL){
delete [] hashTable;
}
}
void createHashTable(int size){//intialize hashtable with linked lists
hashTable=new list<int>[size];
}
void insert(int key,int size){
hashTable[key%size].push_front(key);//inserting key to the front of linked list at hash(key)
}
bool deleteKey(int key,int size){
list<int> l=hashTable[key%size];//if key is present it should be in the list at index=key mod size
list<int>::iterator it;
if(l.empty())
return false; //list empty means delete failed
else{
for (it=l.begin(); it!=l.end(); ++it)//search the list for key
{
if(*it==key)
{
l.erase(it); //if found erase element from list
hashTable[key%size]=l;//copy modified list back to hashtable
return true;
}
}
return false;
}
}
void search(int key,int size){
list<int> l=hashTable[key%size];//if key is present it should be in list at index=key mod size
list<int>::iterator it;
int index=0;
if(l.empty())
cout<<key<<":NOT_FOUND"<<endl;//list empty means not found
else{
for (it=l.begin(); it!=l.end(); ++it)//search list
{
if(*it==key)
{
cout<<key<<":Found_At "<<(key%size)<<","<<index<<endl;
return;
}
index++;
}
cout<<key<<":NOT_FOUND"<<endl;
}
}
void output(int size){
list<int> l;
list<int>::iterator it;
for(int i=0;i<size;i++){
l=hashTable[i];//take each list from hashtable
if(l.empty())
{
cout<<i<<":null"<<endl;
}
else{
cout<<i<<":";//print hashtable index
for (it=l.begin(); it!=l.end(); ++it)//print list
{
cout<< *it<<"->";
}
cout<<endl;
}
}
}
};
int main()
{
int size,key;
cin>>size;
char ch;
HashTable table;
table.createHashTable(size);
cin>>ch;
while(ch!='e'){
if(ch=='i'){
cin>>key;
table.insert(key,size);
}else if(ch=='d'){
cin>>key;
if(table.deleteKey(key,size))
cout<<key<<":DELETED"<<endl;
else
cout<<key<<":DELETE_FAILED"<<endl;
}else if(ch=='s'){
cin>>key;
table.search(key,size);
}else if(ch=='o'){
table.output(size);
}
cin>>ch;
}
return 0;
}