Skip to content
Home » Hashing Functions

Hashing Functions

Below is a clear, complete, exam-oriented explanation of Hashing Functions — suitable for BCA, MCA, and university-level exams.

⭐ Hashing Functions – Introduction

A hashing function (or hash function) is a function that converts a given key (data item) into a fixed-size value called a hash value or hash code.

This hash value is used to determine the index (location) where the key is stored in a hash table.

Purpose of Hashing:

✔ Fast search
✔ Fast insertion
✔ Fast deletion
✔ Efficient data retrieval in average O(1) time

⭐ What is Hashing?

Hashing is a technique of mapping large keys to smaller values (indices) using a hash function so that searching becomes very efficient.

⭐ Properties of a Good Hash Function

A good hash function should:

  1. Be easy to compute
  2. Distribute keys uniformly over the hash table
  3. Minimize collisions (two keys mapping to the same index)
  4. Use entire table space
  5. Be consistent (same input → same output)

⭐ Hash Function Notation

Let:

  • Key = (k)
  • Table size = (m)

Hash function:
[
h(k) = \text{index between } 0 \text{ and } m-1
]

⭐ Types of Hashing Functions

There are several standard hashing techniques used in data structures:

1️⃣ Division Method (Mod Method)

[
h(k) = k \mod m
]

Choose table size (m) as a prime number to reduce collisions.

Example

k = 50, m = 7

[
h(50) = 50 \mod 7 = 1
]

2️⃣ Multiplication Method

[
h(k) = \lfloor m (kA \mod 1) \rfloor
]

Where:

  • A = constant (0 < A < 1), commonly 0.618033 (fraction of golden ratio)
  • m = table size

This method provides better distribution.

3️⃣ Mid-Square Method

  • Square the key
  • Extract middle digits
  • Use as hash value

Example

k = 123
[
k^2 = 15129
]

Middle digits = “12” → hash value.

4️⃣ Folding Method

  • Break the key into parts of equal size
  • Add them together
  • Take mod if needed

Example

Key = 123456
Parts = 12, 34, 56
Sum = 102
Index = 102 mod table_size

5️⃣ Digit Extraction Method

Specific digits of the key are selected to form hash value.

Used when we know which digits give uniformity.

6️⃣ Universal Hashing

Uses a randomly chosen hash function from a family of hash functions to minimize worst-case collisions.

⭐ Collisions in Hashing

A collision occurs when:

[
h(k_1) = h(k_2) \quad \text{and} \quad k_1 \neq k_2
]

Collisions cannot be avoided completely — but can be reduced.

⭐ Collision Resolution Techniques

1. Open Addressing

  • Linear Probing
  • Quadratic Probing
  • Double Hashing

2. Separate Chaining

  • Linked list used at each index of hash table
  • Simple and widely used

If you want, I can explain these in detail.

⭐ Applications of Hashing

✔ Hash tables (search O(1))
✔ Compilers (symbol tables)
✔ Databases (indexing)
✔ Cryptography (cryptographic hash functions)
✔ Password storage
✔ File organization
✔ Caches & memory management

⭐ Advantages of Hashing

  • Very fast access (average O(1))
  • Efficient memory usage
  • Good for large datasets

⭐ Disadvantages

  • Collisions
  • Difficult to order data
  • Table resizing overhead
  • Poor performance if hash function is weak