Hash Maps in C++ Made Simple 🚀

Rehan shaikh — Mon, 17 Aug 2026 17:03:32 +0000

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;
}

DEV Community: Rehan shaikh

Hash Maps in C++ Made Simple 🚀

1. What is a Hash Map?

2. Why Do We Use Hash Maps?

Example: Character Frequency

3. map vs unordered_map

Use unordered_map when:

Use map when:

4. Creating a Hash Map

Unordered Map

Ordered Map

5. Insertion and Updating

Method 1: Using []

Method 2: Using insert()

6. Accessing Elements

Using []

Using .at()

7. Checking Whether a Key Exists

Using count()

Using find()

8. Deletion

9. Size and Empty Check

10. Iterating Through a Map

Range-Based Loop

Why .first and .second?

11. Hash Function

12. Compression Function

13. Bucket Array

14. Hash Collision

15. Collision Resolution Techniques

A. Separate Chaining

Advantage

B. Open Addressing

Linear Probing

Quadratic Probing

Double Hashing

16. Load Factor

Formula

Why is Load Factor Important?

17. Rehashing

18. Time Complexity

19. Common Use Cases

Frequency Counting

Checking Duplicates

First Non-Repeating Character

Two Sum

Caching

Quick Revision Cheat Sheet

3. `map` vs `unordered_map`

Use `unordered_map` when:

Use `map` when:

Method 1: Using `[]`

Method 2: Using `insert()`

Using `[]`

Using `.at()`

Using `count()`

Using `find()`

Why `.first` and `.second`?