Question

Develop an algorithm to demonstrate hashing using hash table with modulo as the hash function. Assume the size of the hash table as 10. To avoid collisions in case of identical keys for two different elements, use Linear Probing collision resolution technique.

using c++

add comment on the code

Answer 1

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int SIZE = 10;//table size 10

//node for hash table for linear probing
class Node
{
public://attributes
int key;
int value;
Node(int key, int value)//constructor
{
this->key = key;
this->value = value;
}
};

//to delete node from table
class ClearNode:public Node
{
private:
static ClearNode *item;
ClearNode():Node(-1, -1)
{}
public:
static ClearNode *getNode()
{
if (item == NULL)
item = new ClearNode();
return item;
}
};
ClearNode *ClearNode::item = NULL;

class HashTable//class for hash table
{
private://attribute
Node **hashtable;
public:
HashTable()//cnstructor
{
hashtable = new Node* [SIZE];//creating hash table with size 10
for (int i = 0; i < SIZE; i++)
{
hashtable[i] = NULL;
}
}

~HashTable()//deleting table
{
for (int i = 0; i < SIZE; i++)
{
if (hashtable[i] != NULL && hashtable[i] != ClearNode::getNode())
delete hashtable[i];
}
delete[] hashtable;
}
//modulo hash function
int HashFunc(int key)
{
return key % SIZE;
}
//method to insert into hash table
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (hashtable[hash_val]
== ClearNode::getNode() || hashtable[hash_val]
!= NULL && hashtable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (hashtable[hash_val] == ClearNode::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hashtable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
hashtable[deletedindex] = new Node(key, value);
else
hashtable[hash_val] = new Node(key, value);
}
if(init != hash_val)
{
if (hashtable[hash_val] != ClearNode::getNode())
{
if (hashtable[hash_val] != NULL)
{
if (hashtable[hash_val]->key == key)
hashtable[hash_val]->value = value;
}
}
else
hashtable[hash_val] = new Node(key, value);
}
}
  
   //method to remove element from hash table   
void Remove(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (hashtable[hash_val]
== ClearNode::getNode() || hashtable[hash_val]
!= NULL && hashtable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && hashtable[hash_val] != NULL)
{
delete hashtable[hash_val];
hashtable[hash_val] = ClearNode::getNode();
}
}
};

int main()
{
HashTable hash;
int key, value;
int choice;
while(1)
{
cout<<" Hash Table Using linear probing"<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Stop"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element: ";
cin>>value;
cout<<"Enter key: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key: ";
cin>>key;
hash.Remove(key);
break;
case 3:
exit(1);
default:
cout<<"\nInvalid option\n";
}
}
return 0;
}

output:

Hash Table Using linear probing
1.Insert
2.Delete
3.Stop
Enter your choice: 1
Enter element: 1
Enter key: 2
Hash Table Using linear probing
1.Insert
2.Delete
3.Stop
Enter your choice: 2
Enter key: 2
Hash Table Using linear probing
1.Insert
2.Delete
3.Stop
Enter your choice: 3

Process exited with return value 1
Press any key to continue . . .