C++ Program to Implement Hash Table using Linear Probing

August 08, 2026

C++ Program to Implement Hash Table using Linear Probing

Introduction

In this C++ program, we will learn how to implement a Hash Table using Linear Probing. A hash table is a data structure that stores elements using a hash function to determine their index. In this program, the hash function key % SIZE is used to calculate the initial index. If the calculated position is already occupied, Linear Probing is used to find the next available position. The program also displays the hash table and allows the user to search for an element.

C++ Program


#include <bits/stdc++.h>
using namespace std;

int main()
{
    const int SIZE = 10;
    int hashTable[SIZE];

    // Initialize hash table
    for(int i = 0; i < SIZE; i++)
    {
        hashTable[i] = -1;
    }

    int num, key, index, start, search;

    cout << "Enter number of elements: ";
    cin >> num;

    if(num > SIZE)
    {
        cout << "Hash table can store maximum "
             << SIZE << " elements." << endl;
        return 0;
    }

    cout << "Enter " << num << " elements:" << endl;

    // Insertion
    for(int i = 0; i < num; i++)
    {
        cin >> key;

        index = key % SIZE;
        start = index;

        // Linear probing
        while(hashTable[index] != -1)
        {
            index = (index + 1) % SIZE;

            if(index == start)
            {
                cout << "Hash table is full." << endl;
                return 0;
            }
        }

        hashTable[index] = key;
    }

    // Display
    cout << "\nElements of hash table:" << endl;

    for(int i = 0; i < SIZE; i++)
    {
        cout << i << " --> ";

        if(hashTable[i] == -1)
            cout << "Empty";
        else
            cout << hashTable[i];

        cout << endl;
    }

    // Searching
    cout << "\nEnter element to search: ";
    cin >> search;

    index = search % SIZE;
    start = index;

    while(hashTable[index] != -1)
    {
        if(hashTable[index] == search)
        {
            cout << "Element found at index "
                 << index << endl;
            return 0;
        }

        index = (index + 1) % SIZE;

        if(index == start)
        {
            break;
        }
    }

    cout << "Element not found." << endl;

    return 0;
}

Sample Output


Enter number of elements: 6

Enter 6 elements:
23 43 13 27 37 17

Elements of hash table:
0 --> Empty
1 --> Empty
2 --> Empty
3 --> 23
4 --> 43
5 --> 13
6 --> 27
7 --> 37
8 --> 17
9 --> Empty

Enter element to search: 37
Element found at index 7

Explanation

Step 1

Define the size of the hash table and create an integer array.


const int SIZE = 10;
int hashTable[SIZE];

Here, the hash table contains 10 positions, from index 0 to 9.

Step 2

Initialize every position of the hash table with -1. The value -1 is used to represent an empty position.


for(int i = 0; i < SIZE; i++)
{
    hashTable[i] = -1;
}

Step 3

Read the number of elements that the user wants to insert. The program also checks whether the number of elements exceeds the hash table size.


cout << "Enter number of elements: ";
cin >> num;

if(num > SIZE)
{
    cout << "Hash table can store maximum "
         << SIZE << " elements." << endl;
    return 0;
}

Since the hash table has only 10 positions, it cannot directly store more than 10 elements.

Step 4

Calculate the initial index using the hash function.


index = key % SIZE;
start = index;

The hash function used in this program is:

Hash Function:


index = key % SIZE

For example, if the key is 23:


index = 23 % 10
      = 3

Therefore, 23 is initially placed at index 3.

Step 5

If the calculated index is already occupied, the program uses Linear Probing. It checks the next position one by one until an empty position is found.


while(hashTable[index] != -1)
{
    index = (index + 1) % SIZE;

    if(index == start)
    {
        cout << "Hash table is full." << endl;
        return 0;
    }
}

hashTable[index] = key;

The expression:


index = (index + 1) % SIZE;

moves to the next position and also allows the search to wrap around from the last index back to index 0.

For example, if index 9 is occupied, the next index will be:


(9 + 1) % 10 = 0

Step 6

After inserting all elements, the program displays every position of the hash table.


for(int i = 0; i < SIZE; i++)
{
    cout << i << " --> ";

    if(hashTable[i] == -1)
        cout << "Empty";
    else
        cout << hashTable[i];

    cout << endl;
}

If the value is -1, the position is displayed as Empty. Otherwise, the stored element is displayed.

Step 7

To search for an element, the same hash function is first used to calculate its initial index.


index = search % SIZE;
start = index;

The program then checks the hash table using the same linear probing sequence used during insertion.

Step 8

If the element is found, its index is displayed and the program terminates. Otherwise, the program continues probing until it reaches an empty position or returns to the starting index.


while(hashTable[index] != -1)
{
    if(hashTable[index] == search)
    {
        cout << "Element found at index "
             << index << endl;
        return 0;
    }

    index = (index + 1) % SIZE;

    if(index == start)
    {
        break;
    }
}

Dry Run

Input


Hash Table Size = 10

Elements = {23, 43, 13, 27, 37, 17}

Search Element = 37

Processing

Element	Hash Calculation	Initial Index	Probing	Final Index
23	23 % 10	3	3 is Empty	3
43	43 % 10	3	3 occupied → 4	4
13	13 % 10	3	3 occupied → 4 occupied → 5	5
27	27 % 10	7	7 is Empty	7
37	37 % 10	7	7 occupied → 8	8
17	17 % 10	7	7 occupied → 8 occupied → 9	9

Final Hash Table

Index	Value
0	Empty
1	Empty
2	Empty
3	23
4	43
5	13
6	Empty
7	27
8	37
9	17

Searching for 37


37 % 10 = 7

Index 7 contains 27, so linear probing moves to index 8. Index 8 contains 37, so the element is found.

Output


Element found at index 8

Time Complexity

Operation	Average Case	Worst Case
Insertion	O(1)	O(n)
Searching	O(1)	O(n)
Display	O(n)	O(n)

Overall Time Complexity: O(n)

In the average case, insertion and searching in a hash table are approximately O(1). However, when many collisions occur, linear probing may require checking multiple positions, resulting in O(n) in the worst case.

Space Complexity

Hash Table Storage: O(n)
Extra Variables: O(1)

Overall Space Complexity: O(n)

Key Points

Uses an array to implement a hash table.
The hash function used is key % SIZE.
Collisions are handled using Linear Probing.
Linear probing checks the next available position sequentially.
The expression (index + 1) % SIZE provides circular probing.
The value -1 represents an empty position.
Average insertion and searching time is O(1).
Worst-case insertion and searching time is O(n).

Keywords

C++ Hash Table, Hash Table in C++, Hashing in C++, Linear Probing in C++, Hash Table using Linear Probing, Collision Resolution in Hashing, Hash Function in C++, C++ Hashing Program, Hash Table Implementation, Linear Probing Algorithm, Data Structures in C++, C++ DSA Programs, C++ Coding Practice, Hashing Interview Questions.

Conclusion

This program demonstrates how to implement a Hash Table using Linear Probing in C++. The program uses the hash function key % SIZE to calculate the initial position of each element. When a collision occurs, Linear Probing is used to find the next available position. The program also demonstrates how to display the hash table and search for an element. Hash tables provide efficient average-case insertion and searching with a time complexity of O(1), making them an important data structure for fast data retrieval.

Search This Blog

1PRINTF

Featured

Merge Sort in C++