GATE CSEIT/Database/ Hashing introduction with hashing function and hashing table

GATE CSEIT/Database/ Hashing introduction with hashing function and hashing table

 Hashing in Databases – GATE CSE/IT

 What is Hashing?

Hashing is a technique used in databases, data structures, and indexing to store and retrieve data efficiently. It uses a hash function to map keys to a specific location in a hash table.

Key Benefits of Hashing:

• Fast data retrieval – O(1) time complexity in the best case.
• Efficient storage – Reduces search time compared to linear search or binary search.
• Indexing in databases – Used in B-Trees, hash indexes, and NoSQL databases.

 Hashing Function

A hash function is a mathematical function that converts a key into a unique index (hash value).

Formula for Hash Function:

$$h(K)=K\mathrm{mod}M$$

where:

• K = Key
• M = Size of the hash table (number of available slots)

Example:

If we insert the key 25 into a hash table of size 10, using h(K) = K mod 10:

$$h(25)=25\mathrm{mod}10=5$$

So, 25 is stored at index 5 in the hash table.

Good Hash Functions Should:
 Be fast to compute.
 Distribute keys uniformly across the table.
 Minimize collisions.

 Hash Table

A hash table is a data structure that stores key-value pairs and uses hashing for fast lookups.

Operations on a Hash Table:
Insertion – Store data at the index calculated by the hash function.
Search – Retrieve data using the hash function.
Deletion – Remove data from the hash table.

Example of a Hash Table (Size = 10):

 If we need to search for key 25, we compute h(25) = 5, and directly access index 5 → O(1) time complexity.

 Types of Hash Functions

1. Division Method (Modulo Method)

$$h(K)=K\mathrm{mod}M$$

 Simple and commonly used.
 M should be a prime number to reduce collisions.

2. Multiplication Method

$$h(K)=\lfloor M(K\times A\mathrm{mod}1)\rfloor$$

where A is a fractional constant (e.g., 0.618).
 Works well with power-of-2 table sizes.

3. Folding Method
 Splits key into parts, applies arithmetic operations, and combines the results.

4. Mid-Square Method
 Squares the key and extracts middle digits as the hash value.

5. Universal Hashing
 Uses randomly chosen hash functions to minimize collisions.

 Collision in Hashing

What is a Collision?
A collision occurs when two different keys hash to the same index in the hash table.

Example:
For M = 10, if keys 25 and 35 both hash to index 5 (h(25) = 5, h(35) = 5), we have a collision.

Collision Handling Techniques:
Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
Separate Chaining (Using Linked Lists)

 Example GATE Question (Hashing Function & Hash Table)

Question: A hash function is defined as h(K) = K mod 7. Given keys 50, 700, 76, 85, 92, 73, insert them into a hash table of size 7.

Solution:
 Compute the hash values.

Final Hash Table (Using Linear Probing):

 Summary

Hashing is a technique for efficient data storage and retrieval.
Hash functions map keys to hash values.
Collisions occur when multiple keys map to the same index.
Collision handling techniques (Open Addressing & Separate Chaining) prevent data loss.
Common GATE questions test hashing functions, collision resolution, and hash table operations.

 Need more GATE practice questions or coding examples? Let me know!

GATE CSEIT/Database/ Hashing introduction with hashing function and hashing table

Introduction to Hash Table and Hash Function

Hashing in Data Structure