What is Hashing?
Hashing is a technique to uniquely identify or map data of arbitrary size into fixed-size values, often called a hash value or hash code.
Think of it as assigning a “digital fingerprint” to your data.
For example:
- If you have a student’s name "Rahul" and apply a hash function, it will generate a fixed hash code, say 1052.
- Another name "Muskan" might generate 9987.
Even though the data size (length of names) is different, the hash function maps them into a fixed range.
Why is Hashing Important?
Hashing is widely used in computer science because it allows for:
1. Fast Data Retrieval → Quick lookup in hash tables (average O(1) time complexity).
2. Efficient Indexing → Used in databases for faster searching.
3. Secure Storage → Passwords are stored as hashes, not plain text.
4. Data Integrity → Hashing verifies data hasn’t been tampered with (e.g., in file transfers).
5. Cryptography → Essential in algorithms like SHA (Secure Hash Algorithm) and MD5.
Real-Life Examples of Hashing
- Login Systems: Your password is not stored directly; instead, its hash is stored.
- File Sharing Apps: Torrents use hashing to check file integrity.
- Databases: Indexing often uses hashing to quickly locate records.
- Caching: Web browsers and servers hash URLs to store cached pages.
Hash Functions
A hash function is the heart of hashing. It takes input data and generates a fixed-size hash code.
Properties of a Good Hash Function:
1. Deterministic → Same input always gives the same output.
2. Fast Computation → Should be quick to calculate.
3. Uniform Distribution → Avoids clustering of values.
4. Collision Resistant → Minimizes cases where two inputs give the same hash.
5. Irreversible (in cryptography) → Hard to reverse-engineer the original data.
Types of Hashing Techniques
Let’s explore different hashing methods with examples.
1. Division Method
This is the simplest method.
Formula:
h(k) = k % m
Where:
- k = key
- m = size of hash table
Example:
Suppose we have keys: 10, 22, 31, 4, and a hash table of size 7.
10 % 7 = 3
22 % 7 = 1
31 % 7 = 3
4 % 7 = 4
Here, 10 and 31 collide since both map to index 3.
2. Multiplication Method
Formula:
h(k) = floor(m * (k * A % 1))
Where A is a constant (0 < A < 1).
This method reduces clustering compared to division.
3. Mid-Square Method
Square the key and extract middle digits.
Example:
Key = 123 → Square = 15129 → Middle digits = 12 → Index = 12.
4. Folding Method
Break the key into parts and add them together.
Example:
Key = 123456 → Split into 12, 34, 56 → Sum = 102 → Index = 102.
5. Double Hashing
Uses two hash functions to reduce collisions.
h(k) = (h1(k) + i * h2(k)) % m
where i is the attempt number.
Collision Handling in Hashing
A collision happens when two keys map to the same hash index. This is unavoidable, but we can handle it.
Methods of Collision Resolution:
1. Chaining
- Each table index holds a linked list.
- Colliding keys are stored in the same list.
Example:
Index 3 → [10 → 31]
2. Open Addressing
- All elements are stored in the hash table itself.
- If a spot is occupied, probe for the next available slot.
Types:
- Linear Probing → Move sequentially.
- Quadratic Probing → Move using square increments.
- Double Hashing → Use another hash function for probing.
Applications of Hashing
1. Password Protection → Store hashed passwords.
2. Data Structures → Implement hash tables and sets.
3. Cryptography → Digital signatures, blockchain, etc.
4. Databases → Hash indexing for quick access.
5. File Systems → Hashing helps in data retrieval.
Example Program in C++
Copy Code
#include <iostream>
#include <list>
using namespace std;
class HashTable {
int BUCKET;
list<int>* table;
public:
HashTable(int V) {
BUCKET = V;
table = new list<int>[BUCKET];
}
int hashFunction(int x) {
return (x % BUCKET);
}
void insertItem(int key) {
int index = hashFunction(key);
table[index].push_back(key);
}
void displayHash() {
for (int i = 0; i < BUCKET; i++) {
cout << i;
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
};
int main() {
HashTable h(7);
int arr[] = {10, 22, 31, 4, 15, 28};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++)
h.insertItem(arr[i]);
h.displayHash();
return 0;
}Output:
0
1 --> 22
2 --> 15
3 --> 10 --> 31
4 --> 4
5 -->
6 --> 28
Advantages of Hashing
- Very fast lookups (O(1) on average).
- Saves memory compared to arrays for large key ranges.
- Useful in both storage and security.
Disadvantages of Hashing
- Collisions can occur.
- Poorly designed hash functions lead to clustering.
- Hash tables are not ordered, unlike trees.
FAQs on Hashing
Q1. What is hashing in simple words?
Hashing is a process of converting data into a fixed-size code (hash value) using a hash function.
Q2. What are the main applications of hashing?
Hashing is used in password protection, cryptography, database indexing, file systems, and caching.
Q3. How do you handle collisions in hashing?
Using chaining (linked lists) or open addressing methods like linear probing, quadratic probing, and double hashing.
Q4. Is hashing better than searching with arrays?
Yes, because hashing provides O(1) average search time compared to O(n) in linear search.
Q5. What is the difference between hashing and encryption?
- Hashing is one-way (irreversible) and used for integrity/security.
- Encryption is reversible (data can be decrypted).
Final Thoughts
Hashing is one of the most powerful and practical techniques in computer science. Whether you’re working with data structures, building a database, or implementing a secure login system, hashing will be your go-to tool.
The key is to choose a good hash function and apply the right collision handling technique. Once you master hashing, many advanced concepts like cryptography, blockchain, and distributed systems will become easier to understand.
