GATE CSEIT/Database/Hashing example ( Which clear your all doubt).

GATE CSEIT/Database/Hashing example ( Which clear your all doubt).

Hashing in Databases – GATE CSE/IT Example with Explanation

What is Hashing in Databases?

Hashing is a technique used in databases to quickly access records using a hash function that maps keys to locations in a hash table. It helps in:
Efficient retrieval of data in O(1) average time complexity.
Reducing search time compared to sequential or binary search.
Handling large datasets effectively.

Example 1: Simple Hashing in Database

Problem Statement:

A database contains student records with unique roll numbers (keys). We use a hash function to store and retrieve records efficiently.

Given Data:

Hash Function:

Let’s use Modulo Hashing where the hash function is:

$$h(Key)=Key\mathrm{mod}10$$

This means the roll number will be stored at an index based on its last digit.

Hash Table After Insertion:

Example Query: Searching for roll number 1099
Step 1: Compute h(1099) = 1099 % 10 = 9
Step 2: Go to index 9 → Found! Charlie is stored here.

Example 2: Collision Handling with Chaining

Problem Statement:

Suppose two students have roll numbers 1023 and 1123. Since

$$1023\mathrm{mod}10=1123\mathrm{mod}10=3$$

both will be assigned to index 3 in the hash table. This causes a collision.

Solution:

Use Chaining (Linked List at each index).

Updated Hash Table (with Chaining for index 3):

 Now, when searching for 1123, we check index 3 and traverse the list to find it.

Key Takeaways for GATE Exam

Direct Addressing is inefficient for large keys, so hashing is used.
Modular Hashing (h(key) = key % table_size) is common in GATE problems.
Collisions are handled using:

• Chaining (Linked List at each index)
• Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
  Hashing is efficient (O(1) average case) but can degrade to O(n) in worst case (when all keys hash to the same location).

Would you like more GATE-level problems with solutions?

GATE CSEIT/Database/Hashing example ( Which clear your all doubt).

INFORMATION TECHNOLOGY

Here’s a clear and detailed hashing example tailored for GATE CSE/IT – Database topic to help clear all your doubts about how hashing works, what collisions are, and how collision resolution is done.

Hashing: Crystal Clear Example

Problem:

Insert the following keys into a hash table of size 10 using:

1. Division method: h(k) = k mod 10

2. Use Linear Probing to handle collisions.

Keys to insert:
23, 43, 13, 27, 33

Step 1: Apply Hash Function

For each key:
h(k) = k mod 10

Collision Detection

We see collisions at index 3 for:

• 43 (conflicts with 23)

• 13 (conflicts with 23 and 43)

• 33 (conflicts with 23, 43, 13)

Collision Resolution Using Linear Probing

Linear Probing:
If slot h(k) is occupied, check h(k) + 1, then h(k) + 2, and so on (mod table size).

Insertion Order:

1. 23 → index 3 (free)

2. 43 → index 3 (occupied) → try 4

3. 13 → index 3 (occupied), 4 (occupied) → try 5

4. 27 → index 7 (free)

5. 33 → index 3 → 4 → 5 → try 6

Final Hash Table

Key Concepts You Learned:

• Hash Function: Converts a key to an index.

• Collision: Two keys get same index (e.g., 23, 43, 13, 33 → all map to 3).

• Linear Probing: Find next free slot (sequentially) when a collision occurs.

Try Yourself

Use the same method for keys:
11, 22, 31, 4, 15, 28, 17
with table size = 10
and h(k) = k mod 10

Would you like:

• The same example using chaining?

• A quiz to practice?

• A PDF/visual chart of this process?

Let me know!

GATE CSEIT/Database/Hashing example ( Which clear your all doubt).

UNIT-2 HASHING STATIC HASHING Hash Tables …

DBMS Hashing