Hashing
Hashing is a technique used to store and retrieve data very quickly using a special function called a hash function.
The main idea is:
Convert a key into an index, then use that index to store or find the data.
Hashing is extremely important in DSA because it can often make searching from O(n) to approximately O(1).
1. Why Do We Need Hashing?
Suppose we have:
[10, 25, 35, 42, 56, 78]
If we want to find 56 using a normal array, we may need to check:
10 → 25 → 35 → 42 → 56
This is linear search.
Complexity
O(n)
But what if we could directly calculate where 56 should be?
That's the idea behind hashing.
Key ↓ Hash Function ↓ Index ↓ Data
Then we can potentially find the value in:
O(1)
2. Real-Life Example
Imagine a college has student IDs:
101 102 103 104 ...
Instead of searching through every student's record, we could use the ID to determine where their information is stored.
For example:
Student ID → Hash Function → Storage Location
So:
101 → 1 102 → 2 103 → 3
Then finding student 103 is very fast.
3. Hash Function
A hash function converts a key into an index.
A simple example:
hash(key) = key % table_size
Suppose table size is 10.
For:
key = 27
we calculate:
27 % 10 = 7
So:
27 → index 7
Another:
43 % 10 = 3
Therefore:
43 → index 3
4. Hash Table
A hash table is a data structure that stores data using hash values.
Suppose:
Table size = 10
We insert:
27 43 15
Using:
hash(key) = key % 10
we get:
27 % 10 = 7 43 % 10 = 3 15 % 10 = 5
The table looks conceptually like:
Index Value ---------------- 0 - 1 - 2 - 3 43 4 - 5 15 6 - 7 27 8 - 9 -
So to find 43:
43 % 10 = 3
Go directly to index 3.
5. Hashing vs Array Search
Suppose:
[15, 27, 43, 51, 72]
Array
To search for 72:
15 → 27 → 43 → 51 → 72
Worst case:
O(n)
Hash Table
Calculate:
72 % table_size
Then go to the calculated location.
Average case:
O(1)
That's the major advantage of hashing.
6. Collision
There's an important problem.
What if two keys produce the same index?
This is called a:
Collision
For example, table size = 10.
27 % 10 = 7 37 % 10 = 7 47 % 10 = 7
All three want index 7.
27 ─┐ 37 ─┼──→ index 7 47 ─┘
We need a method to handle this.
7. Collision Handling
Two major methods are:
1. Separate Chaining
2. Open Addressing
Let's understand both.
8. Separate Chaining
In separate chaining, each hash table position stores multiple values, usually using a linked list or another container.
For:
27 37 47
all hash to index 7.
We can store:
Index 7: 7 → [27] → [37] → [47]
Conceptually:
0 1 2 3 4 5 6 7 → 27 → 37 → 47 8 9
This is called chaining because values are chained together.
9. Open Addressing
Another approach is open addressing.
Instead of storing multiple values at the same index, we search for another empty position.
For example:
27 → index 7 37 → index 7 ❌
Index 7 is occupied.
Try another position:
index 8
So:
7 → 27 8 → 37
Then perhaps:
47 → 7 ❌ → 8 ❌ → 9 ✅
Result:
7 → 27 8 → 37 9 → 47
10. Linear Probing
One common open-addressing technique is linear probing.
If the desired index is occupied:
index index + 1 index + 2 index + 3 ...
are checked.
Example:
27 → 7 37 → 7 occupied ↓ 8
So:
7 → 27 8 → 37
11. Quadratic Probing
Instead of checking:
+1 +2 +3 +4
we use squares:
+1² +2² +3² +4²
So:
h(k) h(k) + 1² h(k) + 2² h(k) + 3² ...
This helps reduce some clustering problems found in linear probing.
12. Double Hashing
Another method is double hashing.
We use two hash functions.
index = h1(key) + i × h2(key)
The second hash function determines the jump size.
This can reduce clustering further.
13. Hash Table in C++
In modern C++, we usually don't implement hashing from scratch.
The STL provides:
unordered_map unordered_set
These are hash-based containers.
14. unordered_set
unordered_set stores unique values.
Example:
#include <iostream> #include <unordered_set> using namespace std; int main() { unordered_set<int> s; s.insert(10); s.insert(20); s.insert(30); if (s.find(20) != s.end()) { cout << "Found"; } return 0; }
Output:
Found
15. Important unordered_set Operations
unordered_set<int> s;
Insert
s.insert(10);
Search
s.find(10);
Check existence
if (s.count(10)) { cout << "Found"; }
Delete
s.erase(10);
Size
s.size();
Empty
s.empty();
16. unordered_map
unordered_map stores:
Key → Value
For example:
Student ID → Student Name
101 → Uday 102 → Ram 103 → Sita
C++:
#include <iostream> #include <unordered_map> using namespace std; int main() { unordered_map<int, string> students; students[101] = "Uday"; students[102] = "Ram"; students[103] = "Sita"; cout << students[101]; return 0; }
Output:
Uday
17. unordered_map Operations
Insert
students[101] = "Uday";
Access
cout << students[101];
Search
if (students.find(101) != students.end()) { cout << "Found"; }
Delete
students.erase(101);
Size
students.size();
18. Frequency Counting
This is one of the most important applications of hashing.
Suppose:
[1, 2, 2, 3, 1, 2, 4]
We want to count how many times each number appears.
Use:
unordered_map<int, int> freq;
Then:
for (int x : arr) { freq[x]++; }
Complete example:
#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { vector<int> arr = {1, 2, 2, 3, 1, 2, 4}; unordered_map<int, int> freq; for (int x : arr) { freq[x]++; } for (auto p : freq) { cout << p.first << " -> " << p.second << endl; } return 0; }
Conceptually:
1 → 2 2 → 3 3 → 1 4 → 1
19. Character Frequency
Hashing is also useful with strings.
Suppose:
"banana"
We want:
b → 1 a → 3 n → 2
C++:
unordered_map<char, int> freq; for (char ch : s) { freq[ch]++; }
This is extremely common in DSA problems.
20. Find Duplicate Elements
Suppose:
[1, 2, 3, 2, 4, 1]
We can use a hash set.
unordered_set<int> seen; for (int x : arr) { if (seen.count(x)) { cout << "Duplicate: " << x << endl; } seen.insert(x); }
The set remembers which values we've already seen.
21. Two Sum Problem
This is one of the most famous hashing problems.
Given:
[2, 7, 11, 15]
and:
target = 9
We need two numbers whose sum is 9.
Instead of checking every pair, use a hash map.
For each number:
needed = target - current
For 2:
needed = 9 - 2 = 7
Is 7 already seen?
No.
Store 2.
Then encounter 7:
needed = 9 - 7 = 2
2 is already in the hash table.
Therefore:
2 + 7 = 9
C++ example
#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { vector<int> arr = {2, 7, 11, 15}; int target = 9; unordered_map<int, int> mp; for (int i = 0; i < arr.size(); i++) { int needed = target - arr[i]; if (mp.find(needed) != mp.end()) { cout << mp[needed] << " " << i; return 0; } mp[arr[i]] = i; } return 0; }
The important idea is:
Current value ↓ Calculate what is needed ↓ Search hash table ↓ Found? ↓ Yes → Answer No → Store current value
Average complexity:
Time = O(n) Space = O(n)
A brute-force solution would usually be:
O(n²)
22. Hashing with Strings
Hashing isn't limited to integers.
We can hash:
int string char pair custom objects
For example:
unordered_set<string> names; names.insert("Uday"); names.insert("Ram"); names.insert("Sita");
Search:
if (names.count("Uday")) { cout << "Found"; }
23. map vs unordered_map
This is very important in C++.
map
Usually implemented using a balanced tree.
map<int, string> mp;
Complexity:
Search → O(log n) Insert → O(log n) Delete → O(log n)
Keys are maintained in sorted order.
unordered_map
Hash table.
unordered_map<int, string> mp;
Average:
Search → O(1) Insert → O(1) Delete → O(1)
But elements are not stored in sorted order.
24. set vs unordered_set
Similarly:
| Container | Structure | Average Search | Sorted? |
|---|---|---|---|
set | Tree | O(log n) | Yes |
unordered_set | Hash table | O(1) | No |
And:
| Container | Stores |
|---|---|
set | Unique values |
unordered_set | Unique values |
map | Key → Value |
unordered_map | Key → Value |
25. Hashing Complexity
For unordered_map and unordered_set:
| Operation | Average | Worst Case |
|---|---|---|
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
Why can the worst case become O(n)?
Because many keys can collide and end up in the same bucket.
Good hash distribution keeps operations close to O(1) on average.
26. Load Factor
A hash table has a concept called load factor.
Roughly:
Load Factor = Number of stored elements / Number of buckets
For example:
Elements = 7 Buckets = 10
Then:
Load Factor = 7 / 10 = 0.7
If a hash table becomes too full, collisions can increase.
Hash tables can therefore rehash, meaning they create more buckets and redistribute the elements.
You generally don't need to implement this manually when using unordered_map or unordered_set.
27. Hashing vs Hash Table
Don't confuse these terms.
Hashing
The technique of converting data into a hash value/index.
Hash Function
The function that performs the conversion.
key → hash function → hash/index
Hash Table
The data structure that uses hashing to store data.
Hashing ↓ Hash Function ↓ Hash Table
28. Common DSA Problems Using Hashing
Hashing appears everywhere.
Basic
- Frequency counting
- Find duplicates
- Remove duplicates
- Check existence
- Count distinct elements
Intermediate
- Two Sum
- First non-repeating character
- Anagram checking
- Longest consecutive sequence
- Subarray with given sum
- Count subarrays with sum
K
Advanced
- Longest substring without repeating characters
- Group anagrams
- Frequency-based problems
- Prefix sum + hashing
- Sliding window + hashing
🧠 The Core Hashing Pattern
When you see a problem asking:
"Have I seen this before?"
Think:
unordered_set
When you see:
"How many times does this occur?"
Think:
unordered_map
When you see:
"I need to quickly find a corresponding value."
Think:
unordered_map
For example:
Have I seen 10? ↓ unordered_set How many times did 10 occur? ↓ unordered_map Where did I see 10? ↓ unordered_map<value, index>
🔥 Final Summary
HASHING | ┌────────┴────────┐ ↓ ↓ Hash Function Hash Table | | Key → Index Store / Search | ┌───────────┴───────────┐ ↓ ↓ unordered_set unordered_map ↓ ↓ Unique values Key → Value
Most important points:
- Hashing provides fast data lookup.
- A hash function converts a key into a hash/index.
- Two keys can produce the same index → collision.
- Collision can be handled using chaining or open addressing.
- C++ provides
unordered_setandunordered_map. - Average search/insert/delete is O(1).
- Hashing is extremely useful for frequency counting, duplicates, Two Sum, anagrams, and lookup problems.
map/setare generally O(log n) and sorted.unordered_map/unordered_setare generally O(1) average and not sorted.
Your DSA roadmap now:
Introduction ↓ Complexity Analysis ↓ Arrays ↓ Strings ↓ Linked List ↓ Stack ↓ Queue ↓ Deque ↓ Recursion ↓ Backtracking ↓ ⭐ Hashing ← YOU ARE HERE ↓ Trees ↓ Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie ↓ Graphs ↓ ...