std::unordered_map

std::unordered_map

---

Prerequisites

---

1. What is std::unordered_map?

std::unordered_map is an associative container that stores elements in key-value pairs, just like std::map.

std::unordered_map<Key, Value>

• Keys are unique
• No ordering of elements
• Implemented using a Hash Table
• Provides average O(1) time complexity

std::unordered_map is implemented using a Hash Table

How it works:

1. Key → Hash function
2. Hash → Bucket index
3. Store value in that bucket

Multiple keys may land in the same bucket (collision)

Hash Collision

key1 → hash → bucket 3
key2 → hash → bucket 3

This is called a collision

Handling:

• Chaining (linked list / nodes inside bucket)
• Open addressing (implementation dependent)

Use it when:

• You need fast lookup (O(1))
• Order does not matter
• You handle large datasets

✔️ Declaration

#include <unordered_map>

std::unordered_map<std::string, int> m;

✔️ Insertion

m["apple"] = 10;
m["banana"] = 20;

Or:

m.insert({"orange", 30});

m["new_key"];

If the key does not exist, it will be created automatically with a default value

✔️ Access

std::cout << m["apple"];  // 10

2. Functions

find

auto it = m.find("apple");

if (it != m.end())
    std::cout << it->second;

erase

m.erase("apple");

size

m.size();

clear

m.clear();

Iteration

for (const auto& pair : m)
    std::cout << pair.first << " : " << pair.second << "\n";

Order is not guaranteed

Operation	Complexity
Insert	O(1) average
Search	O(1) average
Delete	O(1) average
Worst Case	O(N)

Worst case happens when hash collisions occur

3. std::map vs std::unordered_map

Feature	unordered_map	map
Structure	Hash Table	Red-Black Tree
Ordering	None	Sorted
Speed	O(1) avg	O(log N)
Worst Case	O(N)	O(log N)
Memory	More	Less

Use unordered_map when performance is critical

4. Common Mistakes

❌ Overusing operator[]

if (m["key"] == 0)  // ❌ Dangerous

Creates key if it doesn’t exist

✔️ Correct:

if (m.find("key") != m.end())

❌ Assuming order

for (auto& p : m)
{
    // ❌ Do NOT expect sorted order
}

5. Custom Hash Function

struct MyHash
{
    size_t operator()(int x) const
    {
        return x * 31;
    }
};

std::unordered_map<int, int, MyHash> m;