Hashing in Data Structures (Complete Beginner Guide with C++)

Introduction

When working with programs, we often need to store data and search it very fast.
Searching data one by one takes time.

Hashing is a technique that helps us store and find data in constant time.

---

What Is Hashing?

Hashing is a process where:

• A key (number or string) is given

• A hash function converts it into a small number

• That number is used as an index in an array

Hashing = Key → Index → Fast Access

---

Why Do We Need Hashing?

Hashing gives the fastest search.

---

What Is a Hash Table?

A hash table is an array where:

• Each index is called a bucket

• Data is stored using a hash function

Index:  0 1 2 3 4 5 6 7 8 9
Value:  - - - - - 25 - - - -

---

What Is a Hash Function?

A hash function converts a key into an array index.

index = hash(key)

Example:

hash(key) = key % table_size

---

Simple Hash Function in C++

int hashFunction(int key, int size) {
    return key % size;
}

---

Example: Basic Hashing in C++

#include <iostream>
using namespace std;

int main() {
    int hashTable[10];

    for (int i = 0; i < 10; i++)
        hashTable[i] = -1;

    int keys[] = {12, 27, 35};

    for (int key : keys) {
        int index = key % 10;
        hashTable[index] = key;
    }

    for (int i = 0; i < 10; i++)
        cout << i << " : " << hashTable[i] << endl;
}

---

Types of Hash Functions (Deep Explanation)

---

1️⃣ Division Method

Idea

Divide the key by table size and take remainder.

Formula

h(key) = key % table_size

Example

Key = 27
Table size = 10
27 % 10 = 7

C++ Code

int divisionHash(int key, int size) {
    return key % size;
}

Why It Works

• Remainder is always within array size

• Very fast

Important Rule 🔥

Use prime table size (11, 13, 17) to reduce collisions.

---

2️⃣ Mid-Square Method

Idea

Square the key and take middle digits.

Steps

1. Square the key

2. Extract middle digits

3. Use them as index

Example

Key = 23
23² = 529
Middle digit = 2

C++ Code

int midSquareHash(int key, int size) {
    int square = key * key;
    int middle = (square / 10) % 100;
    return middle % size;
}

Why It Works

• Squaring mixes digits

• Middle digits reduce pattern collisions

---

3️⃣ Folding Method

Idea

Break key into parts, add them, then apply modulo.

Steps

1. Split key into equal parts

2. Add the parts

3. Apply modulo

Example

Key = 123456
Split → 12 | 34 | 56
Sum → 102
Index → 102 % 10 = 2

C++ Code

int foldingHash(int key, int size) {
    int sum = 0;

    while (key > 0) {
        sum += key % 100;
        key /= 100;
    }
    return sum % size;
}

Why It Works

• Works well for large keys

• Uses all digits of the key

---

Collision in Hashing

A collision happens when two keys give the same index.

27 % 10 = 7
37 % 10 = 7

---

Collision Handling Techniques

---

1️⃣ Chaining

Each index stores a list of values.

#include <vector>
vector<int> hashTable[10];
hashTable[key % 10].push_back(key);

---

2️⃣ Open Addressing (Linear Probing)

If index is full → check next index.

while (table[index] != -1) {
    index = (index + 1) % size;
}

---

Hashing Using C++ STL

unordered_map

#include <unordered_map>
unordered_map<int, string> mp;
mp[1] = "Apple";

unordered_set

#include <unordered_set>
unordered_set<int> s;
s.insert(10);

---

Time Complexity

---

Advantages of Hashing

• Very fast access

• Simple logic

• Efficient for large data

---

Disadvantages of Hashing

• Collisions cannot be avoided

• Data order is not maintained

---

Real-World Applications

• Databases

• Password storage

• Caching

• Compilers

• Blockchain