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

Here’s a focused introduction to Hashing for GATE CSE/IT – Databases, covering:

• What hashing is

• Hash functions

• Hash tables

• Types of collisions and resolution techniques

• Key points for GATE

---

Introduction to Hashing

Hashing is a technique used to map data (keys) to a fixed-size table (hash table) using a hash function.

Purpose:

To support efficient data retrieval in average O(1) time, especially in:

• Indexing

• Symbol tables

• Databases

• Hash-based joins

---

Hash Function

A hash function (h) maps a key k to an index in a hash table:

Where:

• k: key

• h(k): hash value (bucket number)

• m: size of the hash table

Common Hash Functions:

1. Division Method
   h(k) = k mod m
m should be a prime number to reduce collisions.

2. Multiplication Method
   h(k) = floor(m * (k * A mod 1))

   • A: constant (0 < A < 1), often ≈ 0.618

3. Mid-Square Method

   • Square the key and take middle digits.

4. Folding Method

   • Divide key into parts, add them.

---

Hash Table

A hash table is an array-like data structure where:

• Each index is a bucket

• Buckets can store keys or (key, value) pairs

---

Collisions

When two keys hash to the same index:

Collision Resolution Techniques:

1. Open Hashing (Chaining)

• Each bucket holds a linked list of keys.

• Multiple keys can go into the same bucket.

2. Closed Hashing (Open Addressing)

• All elements are stored within the table itself.

• If a collision happens, find the next free slot.

Open Addressing Methods:

• Linear Probing:
  h(k, i) = (h(k) + i) mod m

• Quadratic Probing:
  h(k, i) = (h(k) + c1*i + c2*i²) mod m

• Double Hashing:
  h(k, i) = (h1(k) + i * h2(k)) mod m

---

GATE Concepts and Tips

• Load Factor (α):
  α = n / m
  Where n = number of keys, m = table size
  Affects performance; ideal α < 1

• Understand time complexities:

  • Average case search: O(1)

  • Worst case (due to collisions): O(n)

• Know how hash joins work in DBMS (especially in GATE-level questions).

---

Example

Given:

• Keys: 23, 43, 13, 27

• Table size: m = 7

• Hash function: h(k) = k mod 7

Hash values:

If using chaining, both 13 and 27 are stored in bucket 6’s linked list.

---

Would you like practice questions, previous GATE MCQs on hashing, or visuals/diagrams for easier understanding?

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

Lecture 17 Introduction to Hashing