Question

Insert elements into a hash table implemented using chain hashing, as an array of linked list in which each entry slot is as a linked list of key/value pairings that have the same hash (outcome value computed using certain hash function). You are allowed to use “Hash Function”, h(k) = k % x where, x is the value you will need to decide to use, that you find appropriate for this implementation. The main requirements are the following:

1. Input: read key/value from a file (either read/take input as a text file) or take user input for the key/value (let user enter the whole entries as one key at a time in console interface). Example key are; “How are you?”, 12345, etc.

2. Processing: the input key could be either string (series of characters) or integer value (if input is floating point number either cast it to integer or round down to nearest whole number) and the value is integer data. The program must be able to insert the input key/value to an appropriate hash table’s slots. The hash function necessary to compute h(k) = k % x where x is to be decided by yourself. For example: we have used h(k) = k%x where x values were 10, 12, 13, 100 and also x was equal to size of hash table.

3. Output: display the output as index, key, key (integer value if input is series of characters (string), value. Be creative in displaying output. The main implementation requirements are the following:

4. Use Class in C++ 5. Linked list (array if necessary)

6. Chain Hash table (technique almost similar to linear hashing but allows multiple entries to be inserted in same index, but those keys are inserted as entries in linked list

Completely unsure how to do this problem without using int's or strings

Answer 1

1) Code using C++

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<math.h>
using namespace std;
const int X = 10; //size of hashTable
/*
HashNode is a node in hashTable
*/
class HashNode
{
public:
int key; //integer key
   int value; //integer values in a node
   HashNode* next; //pointer to next element
  
HashNode(int key, int value) //constructor
{
this->key = key;
   this->value = value;
   this->next = NULL;
}
};
/*
* HashMap Class Declaration
*/
class HashMap
{
private:
HashNode** htable; //object of HashNode
public:
HashMap()
{
htable = new HashNode*[X]; // hashTable of size 10
for (int i = 0; i < X; i++)
htable[i] = NULL; //set each node to null
}
~HashMap() //destructor for deleting from memory
{
for (int i = 0; i < X; ++i)
   {
HashNode* entry = htable[i];
while (entry != NULL)
   {
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
}
delete[] htable;
}
/*
Hash Function
*/
int HashFunc(int key)
{
return key % X; //calculate hash value
}

/*
Insert Function to insert an element at a key
*/
void Insert(int key, int value)
{
int hash_val = HashFunc(key); //call to calculate hash value
HashNode* prev = NULL;
HashNode* entry = htable[hash_val];//pointer to hash_val position in hashTable
while (entry != NULL) //traverse untill end of the linked list is not found
{
prev = entry; // end node in linked list
entry = entry->next;
}
if (entry == NULL)
{
entry = new HashNode(key, value);
if (prev == NULL) // not a single element is already present in a list
   {
htable[hash_val] = entry; // add new element at first position in linked list
}
   else
   {
prev->next = entry; //add new element at end of the list
}
}
else
{
entry->value = value;
}
}
/*
Delete an element at a key
Description: It takes key as input, if there are multiple values or nodes in the list
then it deletes last node from the list
*/
void Remove(int key)
{
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
HashNode* prev = NULL;
if (entry == NULL || entry->key != key) //if node at position of hash value is null or input key is not same as key at position(hash value)
{
   cout<<"No Element found at key "<<key<<endl;
return;
}
while (entry->next != NULL)//traverse untill end of the linked list is not found
   {
prev = entry; // one node before the end node in the linked list
entry = entry->next;
}
if (prev != NULL)
{
prev->next = entry->next; //shift pointer of one node before the end node to the null
}
delete entry; //delete end node
cout<<"Element Deleted"<<endl;
}
/*
Searching an element at a key
*/
int Search(int key)
{
bool flag = false;
int hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
while (entry != NULL)// traverse the list
   {
if (entry->key == key)// check if input key is same as key at position of hash val
   {
cout<<entry->value<<" "; //display all values in the list
flag = true;
}
entry = entry->next; //move pointer to net element in the list
}
if (!flag) //if the element is not present
return -1;
}
  
void display()
{
for(int i=0;i<X;i++)// traverse the hash table
{
cout<<"\n"<<i;
HashNode* entry = htable[i];
while (entry != NULL)// traverse the list
   {
cout<<"---> "<<entry->value;
entry = entry->next;
}
}
}
};
/*
main() for displaying Menu and accessing class elements
*/
int main()
{
HashMap hash;
float f;
int key, value,n;
int choice;
while (1)
{
cout<<"\n----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"1.Insert a list of keys and elements into the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Search element from the key"<<endl;
cout<<"4.Delete element at a key"<<endl;
cout<<"5.Dissplay"<<endl;
cout<<"6.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1: // for inserting multiple keys and values
cout<<"How many keys and values you want to insert: " ;
cin>>n;
cout<<"\n Insert key and value(key value): ";
for(int i=0;i<n;i++)
{
cin>>f;
key=std::round(f); //round the key if float
cin>>value;
hash.Insert(key, value);
  
}
break;
case 2: // for inserting single key and value
cout<<"Enter key at which element to be inserted: ";
cin>>f;
cout<<"Enter element to be inserted: ";
cin>>value;
key=std::round(f);
hash.Insert(key, value);
break;
case 3:
cout<<"Enter key of the element to be searched: ";
cin>>f;
key=std::round(f);
cout<<"Element at key "<<f<<" : ";
if (hash.Search(key) == -1)
{
   cout<<"No element found at key "<<f<<endl;
   continue;
   }
break;
case 4:
cout<<"Enter key of the element to be deleted: ";
cin>>f;
key=std::round(f);
hash.Remove(key);
break;
case 5:
cout<<"\n Displaying Data in Hash Table:\n";
hash.display();
break;
case 6:
//exit the application
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}

2) screenshot of code

3) output of code

Note:  program is taking input from console. This program is for accepting key as int and float format. float values are accepted as input key but in program are rounded and stored in integer type variable.