Click to open github consisting code file
1. What is a Hash Map?
A Hash Map is a data structure that stores data as key–value pairs.
Key → Value
"apple" → 5
"cat" → 3
"dog" → 7
Instead of searching through all elements, a hash map uses a hash function to quickly locate the position where a key-value pair should be stored.
Main idea:
Example:
mp["apple"] = 50
Key
"apple"
↓
Hash Function
hash("apple")
↓
Hash Code
983746 ← Code generated by Hash Function
↓
Compression
983746 % 10
↓
Bucket Index
6
↓
Bucket
bucket[6]
↓
Key-Value Pair
("apple", 50)
↓
Value
50
2. Why Do We Use Hash Maps?
Hash Maps are useful when we need to:
- Count frequencies
- Search for data quickly
- Store relationships between keys and values
- Detect duplicates
- Cache data
- Map complex keys such as strings to values
Example: Character Frequency
string s = "banana";
unordered_map<char, int> mp;
for(char ch : s) {
mp[ch]++;
}
Result:
b → 1
a → 3
n → 2
Without a hash map, you might need to manually calculate array indexes:
freq[ch - 'a']++;
That works for lowercase English letters, but hash maps are more flexible when keys are words, strings, IDs, etc.
"apple" → 10
"banana" → 5
"mango" → 8
3. map vs unordered_map
| Feature | unordered_map |
map |
|---|---|---|
| Internal structure | Hash Table | Balanced BST |
| Average search | O(1) | O(log N) |
| Insertion | O(1) average | O(log N) |
| Deletion | O(1) average | O(log N) |
| Order | No guaranteed order | Sorted by key |
| Worst case | O(N) | O(log N) |
Use unordered_map when:
- You need fast lookup.
- Order does not matter.
- You are doing frequency counting.
Use map when:
- Keys must remain sorted.
- You need ordered traversal.
- You need predictable
O(log N)performance.
4. Creating a Hash Map
Unordered Map
unordered_map<string, int> mp;
Ordered Map
map<string, int> mp;
Example:
unordered_map<string, int> marks;
marks["Rehan"] = 90;
marks["Amit"] = 85;
marks["Rahul"] = 75;
5. Insertion and Updating
Method 1: Using []
mp["apple"] = 10;
If "apple" already exists:
Value gets updated.
If it does not exist:
A new key-value pair is created.
Example:
mp["apple"] = 10;
mp["apple"] = 20;
Final result:
apple → 20
Method 2: Using insert()
mp.insert({"apple", 10});
or:
mp.insert(make_pair("apple", 10));
6. Accessing Elements
Using []
cout << mp["apple"];
⚠️ Important:
If the key does not exist:
mp["banana"];
C++ creates the key with a default value.
For:
unordered_map<string, int> mp;
mp["banana"] = 0
So after:
cout << mp["banana"];
The map becomes:
banana → 0
Using .at()
cout << mp.at("apple");
If the key does not exist:
Throws an out_of_range exception.
Therefore:
mp[key] → May create a new key
mp.at(key) → Does NOT create a new key
7. Checking Whether a Key Exists
Using count()
if(mp.count("apple")) {
cout << "Found";
}
For unique-key maps:
1 → Key exists
0 → Key does not exist
Using find()
if(mp.find("apple") != mp.end()) {
cout << "Found";
}
If found:
auto it = mp.find("apple");
cout << it->first; // Key
cout << it->second; // Value
8. Deletion
Delete using a key:
mp.erase("apple");
Example:
Before:
apple → 10
banana → 20
After:
mp.erase("apple");
Result:
banana → 20
9. Size and Empty Check
mp.size();
Returns the number of key-value pairs.
mp.empty();
Returns:
true → Map is empty
false → Map contains elements
10. Iterating Through a Map
Range-Based Loop
for(auto x : mp) {
cout << x.first << " " << x.second << endl;
}
Why .first and .second?
Each element inside a map is stored as a pair:
pair<Key, Value>
Therefore:
x.first
means:
Key
and:
x.second
means:
Value
Example:
unordered_map<string, int> mp;
mp["Apple"] = 10;
mp["Banana"] = 20;
Conceptually:
x = {"Apple", 10}
x.first → "Apple"
x.second → 10
11. Hash Function
A hash function converts a key into a numeric value.
Example:
"apple"
↓
Hash Function
↓
123456
For an integer key:
25 → hash → 25
For a string:
"hello" → hash → some large integer
The exact hash calculation is handled internally by C++.
12. Compression Function
The hash code can be very large.
Example:
Hash Code = 123456789
But if the bucket array has only 10 buckets, we need an index between:
0 to 9
A compression function can do:
hashCode % bucketSize
Example:
123456789 % 10 = 9
Therefore:
Bucket Index = 9
13. Bucket Array
Internally, a hash map has an array of buckets.
Example:
Index
0 → [ ]
1 → [ Key-Value ]
2 → [ ]
3 → [ Key-Value ]
4 → [ Key-Value ]
5 → [ ]
The hash function decides which bucket should store a particular key.
14. Hash Collision
A collision happens when two different keys are assigned to the same bucket.
Example:
"apple" → Index 3
"banana" → Index 3
Both cannot directly occupy the same single position.
So we need collision resolution techniques.
15. Collision Resolution Techniques
A. Separate Chaining
Also commonly called:
Open Hashing
Closed Addressing
Each bucket stores multiple elements, traditionally using a linked list.
Bucket 0 → NULL
Bucket 1 → ("apple", 10)
↓
("banana", 20)
↓
("mango", 30)
Advantage
Multiple elements can exist in the same bucket.
B. Open Addressing
Also called:
Closed Hashing
Open Addressing
All elements are stored directly inside the table.
When a collision occurs:
Find another available position.
Example:
Index 3 → Occupied
Index 4 → Empty
Store element at Index 4
Linear Probing
Search sequentially:
h(k)
h(k) + 1
h(k) + 2
h(k) + 3
Quadratic Probing
Search using quadratic jumps:
h(k) + 1²
h(k) + 2²
h(k) + 3²
Example:
Original Index = 5
5 + 1² = 6
5 + 2² = 9
5 + 3² = 14
Double Hashing
Uses a second hash function to calculate the jump.
Conceptually:
New Position =
h1(key) + i × h2(key)
This generally distributes collisions better than simple linear probing.
16. Load Factor
The load factor tells us how full the hash table is.
Formula
Load Factor = Number of Elements / Number of Buckets
or:
Load Factor = N / B
Example:
Elements = 8
Buckets = 10
Load Factor = 8 / 10 = 0.8
Why is Load Factor Important?
If too many elements are stored:
More collisions
↓
Slower operations
When the load factor becomes too high, the hash table may perform rehashing.
17. Rehashing
When the hash table becomes too full:
More Buckets are Created
↓
All Elements are Recalculated
↓
Elements are Redistributed
Example:
Before:
10 Buckets
8 Elements
Load Factor = 0.8
After rehashing:
20 Buckets
8 Elements
Load Factor = 0.4
This helps maintain efficient average-case performance.
18. Time Complexity
| Operation |
unordered_map Average |
unordered_map Worst |
map |
|---|---|---|---|
| Insert | O(1) | O(N) | O(log N) |
| Search | O(1) | O(N) | O(log N) |
| Delete | O(1) | O(N) | O(log N) |
| Access | O(1) | O(N) | O(log N) |
19. Common Use Cases
Frequency Counting
for(auto x : arr) {
mp[x]++;
}
Checking Duplicates
if(mp.count(x)) {
cout << "Duplicate Found";
}
First Non-Repeating Character
Count frequency
↓
Check elements with frequency = 1
Two Sum
Store previously visited numbers
↓
Search for required complement
Caching
Input
↓
Store Result
↓
Same Input?
↓
Return Cached Result
Quick Revision Cheat Sheet
HASH MAP
│
├── Stores → Key : Value
│
├── unordered_map
│ ├── Average → O(1)
│ └── Unordered
│
├── map
│ ├── O(log N)
│ └── Sorted by Key
│
├── Internal Working
│ ├── Hash Function
│ ├── Hash Code
│ ├── Compression Function
│ └── Bucket Array
│
├── Collision
│ ├── Separate Chaining
│ └── Open Addressing
│ ├── Linear Probing
│ ├── Quadratic Probing
│ └── Double Hashing
│
└── Load Factor
└── N / B
↓
High?
↓
Rehashing
Key takeaway: A hash map trades some extra memory and ordering guarantees for very fast average-case O(1) insertion, lookup, and deletion. It is one of the most important data structures for frequency counting, lookups, caching, and many competitive programming problems.
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
int main() {
// Create an unordered map: Key -> Value
unordered_map<string, int> mp;
// -------- INSERTION --------
// Method 1: make_pair()
pair<string, int> p = make_pair("rehan", 1);
mp.insert(p);
// Method 2: pair constructor
pair<string, int> p2("shaikh", 2);
mp.insert(p2);
// Method 3: [] operator
mp["bhai"] = 3;
// -------- UPDATE --------
// Update value of an existing key
mp["bhai"] = 4;
// -------- ACCESSING --------
// Access using []
cout << "rehan: " << mp["rehan"] << endl;
// Access using at()
cout << "shaikh: " << mp.at("shaikh") << endl;
// -------- UNKNOWN KEY --------
// [] creates the key with default value 0
cout << "Unknown: " << mp["unknownkey"] << endl;
// at() throws an error if key doesn't exist
// cout << mp.at("anotherunknown") << endl;
// -------- SIZE --------
// Total number of key-value pairs
cout << "Size: " << mp.size() << endl;
// -------- CHECK KEY --------
// count() returns 1 if key exists, otherwise 0
cout << "Count for rehan: " << mp.count("rehan") << endl;
// find() returns iterator to the key
if (mp.find("rehan") != mp.end()) {
cout << "rehan is present" << endl;
} else {
cout << "rehan is not present" << endl;
}
// -------- DELETE --------
// Remove key and its value
mp.erase("rehan");
cout << "Size after erase: " << mp.size() << endl;
// -------- RANGE-BASED LOOP --------
// Each element is a key-value pair
// Order is NOT guaranteed in unordered_map
cout << "\nUsing range-based loop:" << endl;
for (auto i : mp) {
cout << i.first << " " << i.second << endl;
}
// -------- ITERATOR --------
// Iterate using an iterator
cout << "\nUsing iterator:" << endl;
unordered_map<string, int>::iterator it = mp.begin();
while (it != mp.end()) {
cout << it->first << " " << it->second << endl;
it++;
}
// -------- ORDERED MAP --------
// map stores keys in sorted order
cout << "\nOrdered map (alphabetical order):" << endl;
map<string, int> ordered_mp;
ordered_mp["zebra"] = 10;
ordered_mp["apple"] = 5;
map<string, int>::iterator idx = ordered_mp.begin();
while (idx != ordered_mp.end()) {
cout << idx->first << " " << idx->second << endl;
idx++;
}
return 0;
}
Top comments (0)