Skip to content
Laviyx Learn

Try

C++ course menu

C++ unordered_map and unordered_set: Hash Tables for Fast Lookup

Learn std::unordered_map and std::unordered_set: O(1) average lookups with hashing, inserting, finding and erasing, counting frequencies, detecting duplicates, the two-sum problem, hashing your own types, and when to choose them over map and set.

Intermediate11 min readUpdated
On this page

std::unordered_map and std::unordered_set are hash tables. They give up keeping elements in order, and in exchange they find, insert and erase elements in constant time on average, no matter how many elements they hold. They are the go-to containers for "look this up fast" and "have I seen this before?".

How hashing works (briefly)#

A hash function turns a key into a number. That number picks a bucket where the element is stored. To find a key, the container hashes it again and looks only in that bucket, instead of searching every element. Occasionally two keys land in the same bucket (a collision); the container handles that, and grows its bucket array as it fills up to keep collisions rare.

unordered_map#

It has almost the same interface as std::map:

C++
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock = {{"pens", 40}, {"books", 12}};

    stock["bags"] = 5;          // insert
    stock["pens"] -= 10;        // update

    if (auto it = stock.find("books"); it != stock.end()) {
        std::cout << "books: " << it->second << '\n';
    }
    std::cout << std::boolalpha << stock.contains("caps") << '\n';
    std::cout << "pens: " << stock.at("pens") << ", items: " << stock.size() << '\n';
}
Output
books: 12
false
pens: 30, items: 3

The same warning applies as with std::map: stock["caps"] would insert "caps". Use find, contains or at to look up.

No order#

Iterating over an unordered container visits elements in an unspecified order, which can change between compilers, runs or after insertions. If you need sorted output, copy the elements into a vector and sort it, or use std::map:

C++
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

int main() {
    std::unordered_map<std::string, int> votes = {{"Ravi", 12}, {"Asha", 30}, {"Meera", 21}};

    std::vector<std::pair<std::string, int>> ranking(votes.begin(), votes.end());
    std::sort(ranking.begin(), ranking.end(),
              [](const auto& a, const auto& b) { return a.second > b.second; });

    for (const auto& [name, count] : ranking) {
        std::cout << name << ' ' << count << '\n';
    }
}
Output
Asha 30
Meera 21
Ravi 12

Counting frequencies#

Counting is the classic use. Each ++counts[x] is O(1) on average, so counting a million items is fast:

C++
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::string text = "mississippi";
    std::unordered_map<char, int> counts;
    for (char c : text) {
        ++counts[c];
    }
    std::cout << "s appears " << counts['s'] << " times, p appears " << counts['p'] << " times\n";
}
Output
s appears 4 times, p appears 2 times

unordered_set: fast membership#

An unordered_set stores unique values. insert returns whether the value was new, which makes duplicate detection a one-liner:

C++
#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> ids = {104, 221, 357, 221, 489, 104};

    std::unordered_set<int> seen;
    for (int id : ids) {
        if (!seen.insert(id).second) {
            std::cout << "duplicate: " << id << '\n';
        }
    }
    std::cout << seen.size() << " unique ids\n";
}
Output
duplicate: 221
duplicate: 104
4 unique ids

A classic: two-sum#

Given a list of numbers and a target, find two numbers that add up to the target. Checking every pair is O(n²). With a hash map from value to index, one pass is enough:

C++
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>

std::pair<int, int> two_sum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> index_of;   // value -> index
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        if (auto it = index_of.find(need); it != index_of.end()) {
            return {it->second, i};
        }
        index_of[nums[i]] = i;
    }
    return {-1, -1};
}

int main() {
    auto [i, j] = two_sum({2, 7, 11, 15}, 9);
    std::cout << i << ' ' << j << '\n';
    auto [a, b] = two_sum({3, 2, 4}, 6);
    std::cout << a << ' ' << b << '\n';
}
Output
0 1
1 2

This "remember what you have seen in a hash table" pattern solves a large number of interview problems in linear time.

Using your own type as a key#

Built-in types and std::string already have hash functions. For your own type, provide == and a hash. One way is a small hash struct:

C++
#include <functional>
#include <iostream>
#include <unordered_set>

struct Point {
    int x = 0;
    int y = 0;
    bool operator==(const Point&) const = default;
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t hx = std::hash<int>{}(p.x);
        std::size_t hy = std::hash<int>{}(p.y);
        return hx ^ (hy << 1);   // combine the two hashes
    }
};

int main() {
    std::unordered_set<Point, PointHash> visited;
    visited.insert({0, 0});
    visited.insert({1, 2});
    visited.insert({0, 0});   // already there

    std::cout << visited.size() << ' ' << std::boolalpha << visited.contains({1, 2}) << '\n';
}
Output
2 true

A hash only has to be consistent with == (equal objects must have equal hashes); a good one also spreads values out evenly.

Performance notes#

  • Lookups are O(1) on average. In the rare worst case (many keys in one bucket) they become O(n).
  • reserve(n) sets up enough buckets for n elements in advance, avoiding repeated rehashing when you know the size.
  • For very small collections, a sorted std::vector or a plain std::map can be just as fast.

Common mistakes#

Practice#

Practice exercise

Write char first_unique(const std::string& s) that returns the first character that appears exactly once, or '_' if there is none. Test it with "swiss" and "aabb".

Show solution
C++
#include <iostream>
#include <string>
#include <unordered_map>

char first_unique(const std::string& s) {
    std::unordered_map<char, int> counts;
    for (char c : s) ++counts[c];
    for (char c : s) {
        if (counts[c] == 1) return c;
    }
    return '_';
}

int main() {
    std::cout << first_unique("swiss") << ' ' << first_unique("aabb") << '\n';
}
Output
w _

The second loop walks the string, not the map, so "first" means the first in the original order.

Key takeaway#

Finished this lesson?

Related lessons

C++C++ std::map: Key-Value Pairs, Lookup, Insert, Erase and IterationLearn std::map in C++: creating maps, inserting and updating with [], insert and insert_or_assign, safe lookups with find, contains and at, erasing, iterating in sorted key order with structured bindings, custom ordering, and multimap.Intermediate13 min readC++C++ std::set: Sorted Unique Values, Lookups and Set OperationsLearn std::set in C++: storing unique values in sorted order, insert and erase, find and contains, lower_bound and upper_bound, removing duplicates from a vector, set union and intersection, custom ordering, and multiset.Intermediate11 min readC++The C++ Standard Template Library (STL): Containers, Iterators and AlgorithmsAn overview of the C++ STL: the three building blocks (containers, iterators, algorithms), sequence vs associative vs unordered containers, container adaptors, how to choose the right container, and Big-O costs of common operations.Intermediate6 min read