C++ Program to Implement Hash Tables with Linear Probing

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

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

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
const int TABLE_SIZE = 5;
```
```
 
```
```
/*
```
```
 * HashNode Class Declaration
```
```
 */
```
```
class HashNode
```
```
{
```
```
    public:
```
```
        int key;
```
```
        int value;
```
```
        HashNode(int key, int value)
```
```
        {
```
```
            this->key = key;
```
```
            this->value = value;
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * DeletedNode Class Declaration
```
```
 */
```
```
class DeletedNode:public HashNode
```
```
{
```
```
    private:
```
```
        static DeletedNode *entry;
```
```
        DeletedNode():HashNode(-1, -1)
```
```
        {}
```
```
    public:
```
```
        static DeletedNode *getNode()
```
```
        {
```
```
            if (entry == NULL)
```

                entry = new DeletedNode();

```
            return entry;
```
```
        }
```
```
};
```
```
DeletedNode *DeletedNode::entry = NULL;
```
```
/*
```
```
 * HashMap Class Declaration
```
```
 */
```
```
class HashMap
```
```
{
```
```
    private:
```
```
        HashNode **htable;
```
```
    public:
```
```
        HashMap()
```
```
        {
```

            htable = new HashNode* [TABLE_SIZE];

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

```
            {
```
```
                htable[i] = NULL;
```
```
            }
```
```
        }
```
```
 
```
```
        ~HashMap()
```
```
        {
```

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

```
            {
```

                if (htable[i] != NULL && htable[i] != DeletedNode::getNode())

```
                    delete htable[i];
```
```
            }
```
```
            delete[] htable;
```
```
        }
```
```
        /*
```
```
         * Hash Function
```
```
         */
```
```
        int HashFunc(int key)
```
```
        {
```
```
            return key % TABLE_SIZE;
```
```
        }
```
```
        /*
```
```
         * Insert Element at a key
```
```
         */
```
```
        void Insert(int key, int value)
```
```
        {
```

            int hash_val = HashFunc(key);

```
            int init = -1;
```
```
            int deletedindex = -1;
```

            while (hash_val != init && (htable[hash_val]

                            == DeletedNode::getNode() || htable[hash_val]

                            != NULL && htable[hash_val]->key != key))

```
            {
```
```
                if (init == -1)
```
```
                    init = hash_val;
```

                if (htable[hash_val] == DeletedNode::getNode())

                    deletedindex = hash_val;

                hash_val = HashFunc(hash_val + 1);

```
            }
```

            if (htable[hash_val] == NULL || hash_val == init)

```
            {
```
```
                if(deletedindex != -1)
```

                    htable[deletedindex] = new HashNode(key, value);

```
                else
```

                    htable[hash_val] = new HashNode(key, value);

```
            }
```
```
            if(init != hash_val)
```
```
            {
```

                if (htable[hash_val] != DeletedNode::getNode())

```
                {
```

                    if (htable[hash_val] != NULL)

```
                    {
```

                        if (htable[hash_val]->key == key)

                            htable[hash_val]->value = value;

```
                    }
```
```
                }
```
```
                else
```

                    htable[hash_val] = new HashNode(key, value);

```
            }
```
```
        }
```
```
        /*
```
```
         * Search Element at a key
```
```
         */
```
```
        int Search(int key)
```
```
        {
```

            int hash_val = HashFunc(key);

```
            int init = -1;
```

            while (hash_val != init && (htable[hash_val]

                            == DeletedNode::getNode() || htable[hash_val]

                            != NULL && htable[hash_val]->key != key))

```
            {
```
```
                if (init == -1)
```
```
                    init = hash_val;
```

                hash_val = HashFunc(hash_val + 1);

```
            }
```

            if (htable[hash_val] == NULL || hash_val == init)

```
                return -1;
```
```
            else
```

                return htable[hash_val]->value;

```
        }
```
```
        /*
```
```
         * Remove Element at a key
```
```
         */
```
```
        void Remove(int key)
```
```
        {
```

            int hash_val = HashFunc(key);

```
            int init = -1;
```

            while (hash_val != init && (htable[hash_val]

                            == DeletedNode::getNode() || htable[hash_val]

                            != NULL && htable[hash_val]->key != key))

```
            {
```
```
                if (init == -1)
```
```
                    init = hash_val;
```

                hash_val = HashFunc(hash_val + 1);

```
            }
```

            if (hash_val != init && htable[hash_val] != NULL)

```
            {
```

                delete htable[hash_val];

                htable[hash_val] = DeletedNode::getNode();

```
            }
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    HashMap hash;
```
```
    int key, value;
```
```
    int choice;
```
```
    while(1)
```
```
    {
```

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

        cout<<"Operations on Hash Table"<<endl;

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

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

        cout<<"2.Search element from the key"<<endl;

        cout<<"3.Delete element at a key"<<endl;

```
        cout<<"4.Exit"<<endl;
```
```
        cout<<"Enter your choice: ";
```
```
        cin>>choice;
```
```
        switch(choice)
```
```
        {
```
```
        case 1:
```

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

```
            cin>>value;
```

            cout<<"Enter key at which element to be inserted: ";

```
            cin>>key;
```
```
            hash.Insert(key, value);
```
```
            break;
```
```
        case 2:
```

            cout<<"Enter key of the element to be searched: ";

```
            cin>>key;
```
```
            if(hash.Search(key) == -1)
```
```
            {
```

                cout<<"No element found at key "<<key<<endl;

```
                continue;
```
```
            }
```
```
            else
```
```
            {
```

                cout<<"Element at key "<<key<<" : ";

                cout<<hash.Search(key)<<endl;

```
            }
```
```
            break;
```
```
        case 3:
```

            cout<<"Enter key of the element to be deleted: ";

```
            cin>>key;
```
```
            hash.Remove(key);
```
```
            break;
```
```
        case 4:
```
```
            exit(1);
```
```
        default:
```

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

```
       }
```
```
    }
```
```
    return 0;
```
```
}
```

$ g++ Linear_Probing.cpp
$ a.out
 
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 100
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 300
Enter key at which element to be inserted: 3
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 500
Enter key at which element to be inserted: 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 600
Enter key at which element to be inserted: 6
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 800
Enter key at which element to be inserted: 8
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 1000
Enter key at which element to be inserted: 10
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
Element at key 3 : 300
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No element found at key 7
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 10
Element at key 10 : 1000
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element at key 6 : 600
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 5
No element found at key 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 700
Enter key at which element to be inserted: 7
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
Element at key 7 : 700
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4
 
------------------
(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.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Hash Tables with Double Hashing

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

Related Posts:

Recommended Articles: