In: Computer Science
Coding language: C++.
• Each functionality component must be implemented as a separate function, though the function does not need to be declared and defined separately
• No global variables are allowed
• No separate.hor.hpp are allowed
• You may not use any of the hash tables, or hashing functions provided by the STL or Boost library to implement your hash table
• Appropriate, informative messages must be provided for prompts and outputs
You must implement a hash table using the linear probing collision strategy and the alder-32 hashing function with an R of 2. Your collision strategy must be implemented as a separate function, though it may be implemented inside your insert/search/delete functions, and should halt an insert / search/delete functions, and should halt an insert/search/delete after table size number of collisions. Your hash function must be implemented as a separate function. Your hash table must store positive integers and contain 20 buckets. No global declarations.
Functionality
SOULTION:
Create class of HashNode that will be the structure of a
node.
Create class of Hashmap with all the functions like
insert,delete,search,print.
Inside insert function ask user for key and value then find hash
value using modulo of bucket size. if the hash value is empty that
means no value is inserted in it then insert this otherwise apply
linear probing.
Inside search function ask user for key and search in our hTable if
its value is -1 then print element does not exist else return vlaue
of respective key.
Inside delete function ask user for key value if it is present in
hTable then delete it otherwise print element does not exist.
Print is the method used to print all key value pair present in
hashmap.
#include<bits/stdc++.h>
using namespace std;
// Declaration of hash node
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};
// Dnode Class Declaration
class Dnode:public HashNode
{
private:
static Dnode *entry;
Dnode():HashNode(-1, -1)
{}
public:
static Dnode *getNode()
{
if (entry == NULL)
entry = new Dnode();
return entry;
}
};
Dnode *Dnode::entry = NULL;
// Bucket size
class Size{
public:
int BucketSize = 20;
};
Size S;
// Hashmap Class with all functions
class HashMap
{
private:
HashNode **htable;
public:
HashMap()
{
htable = new HashNode* [S.BucketSize];
for (int i = 0; i < S.BucketSize; i++)
{
htable[i] = NULL;
}
}
~HashMap()
{
for (int i = 0; i < S.BucketSize; i++)
{
if (htable[i] != NULL && htable[i] !=
Dnode::getNode()){
cout<<i<<" "<<htable[i]<<endl;
delete htable[i];
}
}
delete[] htable;
}
// Hash Function
int HashFunc(int key)
{
return key % S.BucketSize;
}
//collision function
void collision(int &hval,int &init,int &key,int
&deletedindex)
{
while (hval != init && (htable[hval]== Dnode::getNode() ||
htable[hval]
!= NULL && htable[hval]->key != key))
{
if (init == -1)
init = hval;
if (htable[hval] == Dnode::getNode())
deletedindex = hval;
hval = HashFunc(hval + 1);
}
}
// Insertion
void Insert(int key, int value)
{
int hval = HashFunc(key);
int init = -1;
int deletedindex = -1;
collision(hval,init,key,deletedindex);
if (htable[hval] == NULL || hval == init)
{
if(deletedindex != -1)
htable[deletedindex] = new HashNode(key, value);
else
htable[hval] = new HashNode(key, value);
}
if(init != hval)
{
if (htable[hval] != Dnode::getNode())
{
if (htable[hval] != NULL)
{
if (htable[hval]->key == key)
htable[hval]->value = value;
}
}
else
htable[hval] = new HashNode(key, value);
}
else
{
cout<<" the insert was rejected."<<endl;
return ;
}
}
// Searching
int Search(int key)
{
int hval = HashFunc(key);
int init = -1;
int deleteindex=0;
collision(hval,init,key,deleteindex);
if (htable[hval] == NULL || hval == init)
return -1;
else
return htable[hval]->value;
}
// Deletion
void Remove(int key)
{
int hval = HashFunc(key);
int init = -1;
int deletedindex=0;
collision(hval,init,key,deletedindex);
if (hval != init && htable[hval] != NULL)
{
delete htable[hval];
htable[hval] = Dnode::getNode();
}
else
{
cout<<"the integer does not exist"<<endl;
return ;
}
}
// Print full hash
void print()
{
for (int i = 0; i < S.BucketSize; i++)
{
if (htable[i] != NULL && htable[i]->value!=-1){
cout<<i<<"
"<<htable[i]->value<<endl;
}
}
}
};
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<"\n----------------------"<<endl;
cout<<"Functions on Hash Table"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Print Full Hash"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.Search(key) == -1)
{
cout<<"the integer does not exist
"<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
hash.print();
break;
case 5:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}
THANKYOU