Double Hashing in C++

This C++ Program demonstrates operations on Hash Tables with Double Hashing.

Here is source code of the C++ Program to demonstrate Hash Tables with Double Hashing. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ 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;
```
```
}
```

$ g++ Double_Hashing.cpp
$ a.out
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 5
Table Size Too Small
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: Null
Position: 10 Element: Null
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 30
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 40
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 50
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 60
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 70
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 90
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 100
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 100
Position: 3 Element: 90
Position: 4 Element: 80
Position: 5 Element: 70
Position: 6 Element: 60
Position: 7 Element: 50
Position: 8 Element: 40
Position: 9 Element: 30
Position: 10 Element: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: Null
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5000 
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: 5000
Position: 13 Element: 4000
Position: 14 Element: 3000
Position: 15 Element: 2000
Position: 16 Element: 1000
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: 6000
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: 5000
Position: 13 Element: 4000
Position: 14 Element: 3000
Position: 15 Element: 2000
Position: 16 Element: 1000
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Hash Tables Chaining with List Heads

» Next - C++ Program to Implement Hash Tables with Linear Probing

Related Posts:

Recommended Articles: