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 multiplicative string hashing 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

#include<bits/stdc++.h>
using namespace std;

int hashFunction(string s,int size){
        int R=2;
        int hash_value=0;
        int R_power=1;
        for(int i=0;i<s.length();i++){
                char ch=s[i];
                hash_value=(hash_value + (ch - '0') * R_power) % size;
                R_power=(R_power * R) % size;
        }
        return hash_value;
}

void insert(string s,string bucketArray[],int size){
        int hash_value=hashFunction(s,size);
        int number_of_collisions=0;
        while(number_of_collisions<size){
                int new_hash_value=hash_value+number_of_collisions;
                if(bucketArray[new_hash_value]==""){
                        bucketArray[new_hash_value]=s;
                        cout<<"The integer was inserted\n";
                        return;
                }
                number_of_collisions++;
        }
        cout<<"The insert was rejected\n";
}

void search(string s,string bucketArray[],int size){
        int hash_value=hashFunction(s,size);
        int number_of_collisions=0;
        while(number_of_collisions<size){
                int new_hash_value=hash_value+number_of_collisions;
                if(bucketArray[new_hash_value]==s){
                        cout<<"The integer exists on index "<<new_hash_value<<" in the bucketArray\n";
                        return;
                }
                number_of_collisions++;
        }
        cout<<"The integer does not exist\n";
}

void deleteInput(string s,string bucketArray[],int size){
        int hash_value=hashFunction(s,size);
        int number_of_collisions=0;
        while(number_of_collisions<size){
                int new_hash_value=hash_value+number_of_collisions;
                if(bucketArray[new_hash_value]==s){
                        bucketArray[new_hash_value]="";
                        cout<<"The integer was deleted\n";
                        return;
                }
                number_of_collisions++;
        }
        cout<<"The integer does not exist\n";
}

int main(){
        int size=20;
        string bucketArray[size];
        for(int i=0;i<size;i++){
                bucketArray[i]="";
        }
        while(true){
                cout<<"\nPress 1 to insert an integer";
                cout<<"\nPress 2 to search an integer";
                cout<<"\nPress 3 to delete an integer";
                cout<<"\nPress 4 to output the bucketArray";
                cout<<"\nPress 5 to exit";
                cout<<"\nEnter your choice: ";
                int choice;
                cin>>choice;
                if(choice==1){
                        string input;
                        cout<<"\nEnter the integer: ";
                        cin>>input;
                        insert(input,bucketArray,size);
                }else if(choice==2){
                        string input;
                        cout<<"\nEnter the integer: ";
                        cin>>input;
                        search(input,bucketArray,size);
                }else if(choice==3){
                        string input;
                        cout<<"\nEnter the integer: ";
                        cin>>input;
                        deleteInput(input,bucketArray,size);
                }else if(choice==4){
                        bool okay=true;
                        for(int i=0;i<size;i++){
                                if(bucketArray[i]!=""){
                                        cout<<"\n"<<bucketArray[i]<<" is present at index "<<i;
                                        okay=false;
                                }
                        }
                        if(okay){
                                cout<<"\nNo elements to show";
                        }
                        cout<<"\n";
                }else if(choice==5){
                        cout<<"\nThankYou!\n";
                        break;
                }else{
                        cout<<"\nTry Again!\n";
                }
        }
}