dhash cpp

// Program to implement Double Hashing
#include<iostream>
#include<math.h>
#define SIZE 13
using namespace std;

class hashTable{

    private:
        int table[SIZE], elementCount, num;

    public:

        // initialize hash Table
        hashTable(){
            for(int i=0; i < SIZE; i++){
                table[i] = 0;
            }
            elementCount = 0;
            num = 11;
        }

        // method that checks if the hash table is full or not
        bool isFull(){
            if(elementCount == SIZE){
                return true;
            }else{
                return false;
            }
        }


        // method that returns position for a given element
        int h1(int element){
            return element % SIZE;
        }

        int h2(int element){
            return element % num;
        }

        // method that finds the next empty position using quadratic probing
        int doubleHashing(int element){
            bool posFound = false;
            int newPosition = -1;
            int limit = 50, i = 2;
            while(i <= 50){
                newPosition = (i*this->h1(element) + this->h2(element)) % SIZE;
                if(this->table[newPosition] == 0){
                    posFound = true;
                    break;
                }
                else{
                    i++;
                }
            }
            if(posFound){
                return newPosition;
            }else{
                return -1;
            }
        }

        // method that inserts element inside the hash table
        void insert(int element){
            int position;
            // checking if the table is full
            if(this->isFull()){
                cout<<"\nHash Table Full";
                return;
            }

            bool isStored = false;

            position = this->h1(element);

            // checking if the position is empty
            if(table[position] == 0){
                table[position] = element;
                cout<<"\nElement " <<element<<" stored at position " <<position;
                isStored = true;
                elementCount += 1;
            }

            // collision occured hence we do linear probing
            else{
                cout<<"\nCollision has occured for element " <<element<<" at position " <<position<<" finding new Position.";
                position = doubleHashing(element);
                if(position != -1){
                    this->table[position] = element;
                    elementCount += 1;
                    cout<<"\nElement " <<element<<" stored at position " <<position;
                }

            }
            return;
        }

        // method that searches for an element in the table
        // returns position of element if found
        // else returns false
        int search(int element){
            bool found = false;

            int position = this->h1(element);

            if(table[position] == element){
                found = true;
                return position;
            }

            // if element is not found at position returned hash function
            // then we search element using quadratic probing
            else{
                int limit = 50, i = 1;
                int newPosition = -1;
                while(i <= 50){
                    newPosition = (i*this->h1(element) + this->h2(element)) % SIZE;;
                    if(this->table[newPosition] == element){
                        found = true;
                        break;
                    }
                    else{
                        i++;
                    }
                }
                if(found){
                    return newPosition;
                }
                else{
                    cout<<"Element not found";
                    return -1;
                }
            }
        }


        // method to remove an element from the table
        void remove(int element){
            int position = this->search(element);
            if(position != -1){
                table[position] = 0;
                cout<<"\nElement " <<element<<" is Deleted";
                this->elementCount -= 1;
            }else{
                cout<<"\nElement is not present in the Hash Table";
            }
            return;
        }

        // method to display the hash table
        void display(){
            for (int i = 0; i < SIZE; i++){
                cout<<"\n"<<i<<" = "<<table[i];
            }
            cout<<"\nThe number of element is the Table are : " <<this->elementCount;
        }
};

int main(){
    // main function
    hashTable table1;

    // storing elements in table
    table1.insert(12);
    table1.insert(26);
    table1.insert(31);
    table1.insert(17);
    table1.insert(90);
    table1.insert(28);
    table1.insert(88);
    table1.insert(40);
    table1.insert(77);      // element that causes collision at position 0

    // displaying the Table
    table1.display();
    cout<<"\n";

    // printing position of elements
    cout<<"\nThe position of element 31 is : " <<table1.search(31);
    cout<<"\nThe position of element 28 is : " <<table1.search(28);
    cout<<"\nThe position of element 90 is : " <<table1.search(90);
    cout<<"\nThe position of element 77 is : " <<table1.search(77);
    cout<<"\nThe position of element 1 is : " <<table1.search(1);

    cout<<"\n";

    table1.remove(90);
    table1.remove(12);

    table1.display();
}