Question

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 modulo 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

• Your int main must have the menu allowing the user to choose between inserting, searching, deleting, and outputting the integers in your hash table. The user should be able to insert, search, delete, and output as many times as they wish. There should be an option to end the program. (Hint: enum/switch may be used).
• Insert a user specified integer
  • If an insert is rejected due to the collision strategy halting, the function should output that the insert was rejected.
• Search for the first instance of a user specified integer
  • If found, output that the integer exists upon finding the first instance of the integer.
  • If the collision strategy halts, the function should output that the integer does not exist.
  • No error checking required.
• Delete the first instance of a user specified integer
  • If the desired integer is found, the function should tombstone the integer’s slot in the hash table, and report that the integer was deleted.
  • If the collision strategy halts, the function should output that the integer does not exist.
  • No error checking required
• Output all integers in the hash table starting at index 0 along with their index.

Answer 1

1. Create class of HashNode that will be the structure of a node.
2. Create class of Hashmap with all the functions like insert,delete,search,print.
3. 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.
4. 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.
5. Inside delete function ask user for key value if it is present in hTable then delete it otherwise print element does not exist.
6. 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;
}