Hashing — Searching

🌟 What Is Hashing?

Hashing is a method of finding data super fast.
Instead of searching through the whole list, we use a special function called a hash function to calculate where the data should be stored.

Think of it like a smart shortcut.

---

🔑 Basic Idea

Hashing works in two main steps:

1. Take a key (like a roll number or name).
2. Run it through a hash function → get a unique number (called hash value or index).
3. Store the data at that index in a table.

Later, when you want to search the data, you simply compute the same hash value again —
and jump straight to the location.

No scanning. No waiting.
Just direct access.

---

🗂️ Simple Example

Let’s say we want to store student roll numbers in a table of size 10.

Use a simple hash function:

[
h(key) = key % 10
]

Now let’s store roll number 23:

[
h(23) = 23 % 10 = 3
]

So we put 23 in index 3.

If we want to search for 23 later,
we again compute 23 % 10, get 3, and go straight to index 3.

---

🧩 Diagram (Simple Hash Table)

Hash Table (size 10)

Index : Data
------------------
0     :  -
1     :  -
2     :  -
3     :  23   ← h(23)=3
4     :  -
5     :  -
6     :  -
7     :  -
8     :  -
9     :  -

---

🎈 Real-Life Analogy

Imagine a classroom with 100 students.
Instead of shouting everyone’s name to mark attendance,
you say:

“Roll number 37!”

Immediately, the student at seat 37 stands up.

Hashing works exactly like that —
jumping straight to the exact seat (index) without checking anyone else.

---

⚠️ But There’s a Problem: Collisions

Sometimes, two different keys may land on the same index.

Example:

• h(23) = 3
• h(33) = 3

Both keys want to sit at the same seat.

This is called a collision, and it’s very common.

But don’t worry — we have ways to handle it.

---

🛠️ Collision Handling Techniques

1️⃣ Chaining

Each index stores a linked list of elements.

Index 3: 23 → 33 → 43

So if multiple keys land in the same index,
they form a chain.

---

2️⃣ Open Addressing

If an index is occupied, we look for the next empty spot.

Common methods are:

• Linear Probing → check next index
• Quadratic Probing → skip in squares
• Double Hashing → use a second hash function

---

🎨 Diagram: Chaining (Collision Handling)

Hash Table (size 5)

Index : Data
-----------------------
0     :  -
1     :  11 → 21 → 31
2     :  -
3     :  18
4     :  -

Here:

• h(11)=1
• h(21)=1
• h(31)=1

All of them store in index 1, forming a chain.

---

💻 Why Hashing Is Powerful

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

This means hashing gives constant-time performance in most cases.
That’s why hash tables are used in almost every major application —
databases, compilers, caches, dictionaries, etc.