C++ Programming Code Examples

C++ > Data Structures Code Examples

Program to Implement Hash Tables with Double Hashing

Program to Implement Hash Tables with Double Hashing

    #include <iostream>

    #include <cstdlib>

    #define MIN_TABLE_SIZE 10

    using namespace std;

    /* Node Type Declaration     */

    enum EntryType {Legitimate, Empty, Deleted};

    /* Node Declaration     */

    struct HashNode

    {

        int element;

        enum EntryType info;

    };

    /* Table Declaration     */

    struct HashTable

    {

        int size;

        HashNode *table;

    };

    /* Function to Genereate First Hash     */

    int HashFunc1(int key, int size)

    {

        return key % size;

    }

    /* Function to Genereate Second Hash     */

    int HashFunc2(int key, int size)

    {

        return (key * size - 1) % size;

    }

    /* Function to Initialize Table     */

    HashTable *initializeTable(int size)

    {

        HashTable *htable;

        if (size < MIN_TABLE_SIZE)

        {

            cout<<"Table Size Too Small"<<endl;

            return NULL;

        }

        htable = new HashTable;

        if (htable == NULL)

        {

            cout<<"Out of Space"<<endl;

            return NULL;

        }

        htable->size = size;

        htable->table = new HashNode [htable->size];

        if (htable->table == NULL)

        {

            cout<<"Table Size Too Small"<<endl;

            return NULL;

        }

        for (int i = 0; i < htable->size; i++)

        {

            htable->table[i].info = Empty;

            htable->table[i].element = NULL;

        }

        return htable;

    }

    /* Function to Find Element from the table     */

    int Find(int key, HashTable *htable)

    {

        int hashVal= HashFunc1(key, htable->size);

        int stepSize= HashFunc2(key, htable->size);

        while (htable->table[hashVal].info != Empty &&

               htable->table[hashVal].element != key)

        {

            hashVal = hashVal + stepSize;

            hashVal = hashVal % htable->size;

        }

        return hashVal;

    }

    /* Function to Insert Element into the table     */

    void Insert(int key, HashTable *htable)

    {

        int pos = Find(key, htable);

        if (htable->table[pos].info != Legitimate )

        {

            htable->table[pos].info = Legitimate;

            htable->table[pos].element = key;

        }

    }

    /* Function to Rehash the table     */

    HashTable *Rehash(HashTable *htable)

    {

        int size = htable->size;

        HashNode *table = htable->table;

        htable = initializeTable(2 * size);

        for (int i = 0; i < size; i++)

        {

            if (table[i].info == Legitimate)

                Insert(table[i].element, htable);

        }

        free(table);

        return htable;

    }

    /* Function to Retrieve the table     */

    void Retrieve(HashTable *htable)

    {

        for (int i = 0; i < htable->size; i++)

        {

            int value = htable->table[i].element;

            if (!value)

                cout<<"Position: "<<i + 1<<" Element: Null"<<endl;

            else

                cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;

        }

     

    }

    /* Main Contains Menu     */

    int main()

    {

        int value, size, pos, i = 1;

        int choice;

        HashTable *htable;

        while(1)

        {

            cout<<"\n----------------------"<<endl;

            cout<<"Operations on Double Hashing"<<endl;

            cout<<"\n----------------------"<<endl;

            cout<<"1.Initialize size of the table"<<endl;

            cout<<"2.Insert element into the table"<<endl;

            cout<<"3.Display Hash Table"<<endl;

            cout<<"4.Rehash The Table"<<endl;

            cout<<"5.Exit"<<endl;

            cout<<"Enter your choice: ";

            cin>>choice;

            switch(choice)

            {

            case 1:

                cout<<"Enter size of the Hash Table: ";

                cin>>size;

                htable = initializeTable(size);

                break;

            case 2:

                if (i > htable->size)

                {

                    cout<<"Table is Full, Rehash the table"<<endl;

                    continue;

                }

            	cout<<"Enter element to be inserted: ";

            	cin>>value;

                Insert(value, htable);

                i++;

                break;

            case 3:

                Retrieve(htable);

                break;

            case 4:

                htable = Rehash(htable);

                break;

            case 5:

                exit(1);

            default:

               cout<<"\nEnter correct option\n";

           }

        }

        return 0;

    }