GATE CSEIT/Database/Hashing example ( Which clear your all doubt).
GATE CSEIT/Database/Hashing example ( Which clear your all doubt).
Contents [hide]
- 1 Hashing in Databases – GATE CSE/IT Example with Explanation
- 2 Example 1: Simple Hashing in Database
- 3 Problem Statement:
- 4 Given Data:
- 5 Hash Function:
- 6 Hash Table After Insertion:
- 7 Example 2: Collision Handling with Chaining
- 8 Problem Statement:
- 9 Solution:
- 10 Key Takeaways for GATE Exam
- 11 GATE CSEIT/Database/Hashing example ( Which clear your all doubt).
- 12 INFORMATION TECHNOLOGY
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:
| Roll Number | Name |
|---|---|
| 1023 | Alice |
| 1045 | Bob |
| 1099 | Charlie |
| 1121 | David |
Hash Function:
Let’s use Modulo Hashing where the hash function is:
h(Key)=Keymod 10h(Key) = Key \mod 10
This means the roll number will be stored at an index based on its last digit.
Hash Table After Insertion:
| Index | Stored Roll Numbers |
|---|---|
| 0 | – |
| 1 | 1121 |
| 2 | – |
| 3 | 1023 |
| 4 | – |
| 5 | 1045 |
| 6 | – |
| 7 | – |
| 8 | – |
| 9 | 1099 |
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
1023mod 10=1123mod 10=31023 \mod 10 = 1123 \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):
| Index | Stored Roll Numbers |
|---|---|
| 0 | – |
| 1 | 1121 |
| 2 | – |
| 3 | 1023 → 1123 |
| 4 | – |
| 5 | 1045 |
| 6 | – |
| 9 | 1099 |
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?