Do the following program in C Create a item class with and

Do the following program in C++

- Create a item class... with and integer key and value

- Create a Hash class, that has an array of can input a item and uses a hash algorithm to place it in a array of item nodes.

Include the necessary functions...

-Use CHAINING with pointers, when there is a collision.

-Have a function that prints out the array to verify the hashing and collision code works...

Explain each entry you insert into the hash table...

Solution

#include<bits/stdc++.h>

using namespace std;
const int TABLE_SIZE = 128;

/*
* HashNode Class Declaration
*/
class HashNode
{
public:
int key;
int value;
HashNode* next;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
this->next = NULL;
}
};

/*
* HashMap Class Declaration
*/
class HashMap
{
private:
HashNode** htable;
public:
HashMap()
{
htable = new HashNode*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
htable[i] = NULL;
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
HashNode* entry = htable[i];
while (entry != NULL)
{
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
}
delete[] htable;
}
/*
* Hash Function
*/

void Display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
HashNode* entry = htable[i];
while (entry != NULL)
{
cout<<\"Key \"<<entry->key<<\" Value \"<<entry->value<<endl;
entry = entry->next;
//delete prev;
}
}
}
int HashFunc(int key)
{
return key % TABLE_SIZE;
}

/*
* Insert Element at a key
*/
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
HashNode* prev = NULL;
HashNode* entry = htable[hash_val];
while (entry != NULL)
{
prev = entry;
entry = entry->next;
}
if (entry == NULL)
{
entry = new HashNode(key, value);
if (prev == NULL)
{
htable[hash_val] = entry;
}
else
{
prev->next = entry;
}
}
else
{
entry->value = value;
}
}
/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
HashNode* prev = NULL;
if (entry == NULL || entry->key != key)
{
cout<<\"No Element found at key \"<<key<<endl;
return;
}
while (entry->next != NULL)
{
prev = entry;
entry = entry->next;
}
if (prev != NULL)
{
prev->next = entry->next;
}
delete entry;
cout<<\"Element Deleted\"<<endl;
}
/*
* Search Element at a key
*/
int Search(int key)
{
bool flag = false;
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
while (entry != NULL)
{
if (entry->key == key)
{
cout<<entry->value<<\" \";
flag = true;
}
entry = entry->next;
}
if (!flag)
return -1;
}
};
/*
* Main Contains Menu
*/
int main()
{
HashMap hash;
int key, value;
int choice;
while (1)
{
cout<<\"\ ----------------------\"<<endl;
cout<<\"Operations on Hash Table\"<<endl;
cout<<\"\ ----------------------\"<<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.Display\"<<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;
cout<<\"Element at key \"<<key<<\" : \";
if (hash.Search(key) == -1)
{
cout<<\"No element found at key \"<<key<<endl;
continue;
}
break;
case 3:
cout<<\"Enter key of the element to be deleted: \";
cin>>key;
hash.Remove(key);
break;
case 4:
hash.Display();break;
case 5:
return 0;
default:
cout<<\"\ Enter correct option\ \";
}
}
return 0;
}

==================================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ hash.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Display
5.Exit
Enter your choice: 1
Enter element to be inserted: 0
Enter key at which element to be inserted: 20

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Display
5.Exit
Enter your choice: 1
Enter element to be inserted: 0
Enter key at which element to be inserted: 30

----------------------
Operations on Hash Table

----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Display
5.Exit
Enter your choice: 4
Key 20 Value 0
Key 30 Value 0

===================================================

In this code when we insert 20 value at key 0,then it will go correctly but when we try to insert 30 again at key 0,then it will create another node with 30 and attach next to 20 node.So that Collision will be solved

=============================================================

Comment about work