C++ Program to Implement Hash Tables with Quadratic Probing

This C++ Program demonstrates operations on Hash Tables with Quadratic Probing.

Here is source code of the C++ Program to demonstrate Hash Tables with Quadratic Probing. 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 Quadratic Probing

```
 */
```
```
#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;
```
```
};
```
```
/*
```
```
 * Returns whether n is prime or not
```
```
 */
```
```
bool isPrime (int n)
```
```
{
```
```
    if (n == 2 || n == 3)
```
```
        return true;
```
```
    if (n == 1 || n % 2 == 0)
```
```
        return false;
```
```
    for (int i = 3; i * i <= n; i += 2)
```
```
        if (n % i == 0)
```
```
            return false;
```
```
    return true;
```
```
}
```
```
/*
```

 * Finding next prime size of the table

```
 */
```
```
int nextPrime(int n)
```
```
{
```
```
    if (n <= 0)
```
```
        n == 3;
```
```
    if (n % 2 == 0)
```
```
        n++;
```
```
    for (; !isPrime( n ); n += 2);
```
```
    return n;
```
```
}
```
```
/*
```
```
 * Function To Generate Hash
```
```
 */
```
```
int HashFunc(int key, int size)
```
```
{
```
```
    return key % 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 = nextPrime(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 at a key
```
```
 */
```
```
int Find(int key, HashTable *htable)
```
```
{
```

    int pos = HashFunc(key, htable->size);

```
    int collisions = 0;
```

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

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

```
    {
```

        pos = pos + 2 * ++collisions -1;

```
        if (pos >= htable->size)
```
```
            pos = pos - htable->size;
```
```
    }
```
```
    return pos;
```
```
}
```
```
/*
```

 * Function to Insert Element into a key

```
 */
```
```
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 Hash 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 Quadratic Probing"<<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);

            cout<<"Size of Hash Table: "<<nextPrime(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++ Quadratic_Probing.cpp
$ a.out
----------------------
Operations on Quadratic Probing
 
----------------------
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
Size of Hash Table: 5
----------------------
Operations on Quadratic Probing
 
----------------------
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
Size of Hash Table: 11
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 200
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 300
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 400
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 500
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 700
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 800
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 900
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 1100
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 1100
Position: 2 Element: 100
Position: 3 Element: 200
Position: 4 Element: 300
Position: 5 Element: 400
Position: 6 Element: 500
Position: 7 Element: 600
Position: 8 Element: 700
Position: 9 Element: 800
Position: 10 Element: 900
Position: 11 Element: 1000
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 2200
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 3300
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 4400
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 5500
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: 5500
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: 4400
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: 3300
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: 2200
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 with Linear Probing

» Next - C++ Program to Implement Stack

Related Posts:

Recommended Articles: