# hashing

# 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?

| Method | Time |
| --- | --- |
| Linear Search | O(n) |
| Binary Search | O(log n) |
| Hashing | O(1) (average) |

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
    

```plaintext
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.

```plaintext
index = hash(key)
```

Example:

```plaintext
hash(key) = key % table_size
```

---

## Simple Hash Function in C++

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

---

## Example: Basic Hashing in C++

```plaintext
#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

```plaintext
h(key) = key % table_size
```

### Example

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

### C++ Code

```plaintext
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

```plaintext
Key = 23
23² = 529
Middle digit = 2
```

### C++ Code

```plaintext
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

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

### C++ Code

```plaintext
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.

```plaintext
27 % 10 = 7
37 % 10 = 7
```

---

## Collision Handling Techniques

---

### 1️⃣ Chaining

Each index stores a **list of values**.

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

---

### 2️⃣ Open Addressing (Linear Probing)

If index is full → check next index.

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

---

# Hashing Using C++ STL

### unordered\_map

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

### unordered\_set

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

---

# Time Complexity

| Operation | Average Time |
| --- | --- |
| Insert | O(1) |
| Search | O(1) |
| Delete | O(1) |

---

# 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