skip to content

Hash Maps and Sets

unordered_map hashes keys into buckets, rehashes as the load factor grows, and needs a hash and equality for your type. Interviewers ask about worst cases and custom keys.

on this pageshow

explore

questions

6

In C++, when do you choose std::unordered_map over std::map, and what must the key type provide for each?

level: juniorimportance: must knowfreq 80%

answer

  1. buckets versus a sorted tree
  2. average versus guaranteed cost
  3. std::hash plus operator==
  4. iteration order is unspecified

basics

~20 s

std::unordered_map hashes keys into buckets: lookup is O(1) on average but O(n) in the worst case, iteration order is unspecified, and the key needs a hash and equality. std::map keeps keys sorted, guarantees O(log n), and needs only a less-than ordering.

solid answer

~40 s

Choose `std::unordered_map` when you only look keys up by exact value and want the best average speed; choose `std::map` when you need sorted iteration, range queries such as `lower_bound`, or a worst-case bound. `std::unordered_map<Key, T, Hash = std::hash<Key>, KeyEqual = std::equal_to<Key>>` needs a hash and an equality predicate for the key; `std::map<Key, T, Compare = std::less<Key>>` needs only a strict weak ordering, usually `operator<`. That difference matters in practice: `std::pair` and `std::tuple` work as `std::map` keys out of the box but have no `std::hash` specialization, so an `unordered_map` keyed by a pair needs a custom hasher. Its `find` is average O(1) and worst O(`size()`), its iterators are forward-only, and its iteration order is unspecified and can change after any insert that rehashes.

code

cpp · 15 lines
cpp
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> hashed{{"carol", 3}, {"alice", 1}, {"bob", 2}};
    std::map<std::string, int> sorted{{"carol", 3}, {"alice", 1}, {"bob", 2}};

    std::cout << "unordered_map:";
    for (const auto& [name, id] : hashed) std::cout << ' ' << name;  // unspecified order
    std::cout << "\nmap:";
    for (const auto& [name, id] : sorted) std::cout << ' ' << name;  // always sorted
    std::cout << "\nfirst at or after \"b\": " << sorted.lower_bound("b")->first << '\n';
}

go deeper

for a junior

Recall the core difference: std::map is sorted with O(log n) operations, std::unordered_map is hashed with average O(1) lookups and no order.

for a middle

Explain the key requirements, std::hash and operator== versus a comparator, and why pair keys need a custom hasher only in the hash map.

for a senior

Choose by workload: range queries, deterministic output and worst-case bounds favour std::map; exact-key hot paths favour the hash map, confirmed by measurement.

for a principal

Set a default for new code, for example unordered_map for exact-key caches and map for ordered or observable data, and make exceptions need a measurement.

## Two containers, two contracts Both containers map unique keys to values, and their member functions look almost identical, which is why the choice is often made by habit. Their guarantees are not the same: | Property | `std::map` | `std::unordered_map` | |---|---|---| | Structure | ordered by a comparator (a balanced tree in practice) | buckets selected by a hash | | `find`, `insert`, `erase` by key | O(log n) guaranteed | O(1) average, O(n) worst case | | Key requirements | `Compare`, default `std::less<Key>` | `Hash`, default `std::hash<Key>`, and `KeyEqual`, default `std::equal_to<Key>` | | Iteration order | sorted by key | unspecified; changes when the table rehashes | | Iterator category | bidirectional | forward | | Range queries (`lower_bound`, `upper_bound`) | yes | no | | Effect of insert on iterators | none invalidated | all may be invalidated by a rehash | `std::unordered_map` arrived in C++11; `std::map` has been in the library since C++98. ## What the key must provide For **`std::map`**, the key needs an ordering. With the default comparator that means `operator<` on the key type. Built-in types, `std::string`, `std::pair` and `std::tuple` (which compare lexicographically) all work immediately. For **`std::unordered_map`**, the key needs two things that must agree: - a **hash**: by default `std::hash<Key>`, which the library provides for arithmetic types, enumerations, pointers, `std::nullptr_t`, `std::string`, `std::string_view` and a few others; - an **equality**: by default `std::equal_to<Key>`, which calls `operator==`. For any other type, `std::hash<Key>` is a *disabled* specialization and using it is ill-formed. `std::pair<int, int>` is the classic surprise: there is no `std::hash` for pairs or tuples, so `std::unordered_map<std::pair<int, int>, int>` fails to compile (Apple clang 21 starts with `call to implicitly-deleted default constructor of 'std::hash<std::pair<int, int>>'`), while `std::map<std::pair<int, int>, int>` just works. ## Iteration order is not a feature `std::unordered_map` iterates in bucket order, which depends on the hash function, the bucket count and the insertion history. The snippet below printed `bob alice carol` for the hash map with Apple clang 21 and libc++; another library, another bucket count or one more insert can print something else. Code that formats output, writes snapshots or compares test results by iterating an `unordered_map` therefore has a latent bug: - sort the keys first, or - use `std::map` for anything whose order is observable, or - compare containers with `operator==`, which for unordered containers ignores order. ## Picking for a session cache A session cache that maps a session identifier to session state is the textbook `std::unordered_map` case: 1. Lookups are by exact key, from every request. 2. Nobody needs the sessions in key order. 3. The key, an integer or a string, already has a standard hash. It stops being the right choice when the cache must also expire "all sessions with an identifier below X" (a range query), when the output must be deterministic, or when a worst-case latency bound matters more than the average and the keys can be chosen by an adversary. ## Costs beyond big-O The complexity table hides constant factors that often decide the matter: - **Hashing reads the whole key.** `std::hash<std::string>` processes every character of a long key, while a `std::map` comparison stops at the first differing character. With long keys and few elements, a tree can win. - **Both containers allocate a node per element.** In libstdc++ and libc++, `std::map` is a red-black tree whose node holds parent, child and colour fields beside the element; `std::unordered_map` keeps a node with a next pointer (and often a cached hash) plus a separate bucket array. Neither is compact; a sorted `std::vector` or C++23 `std::flat_map` is, for read-mostly data. - **Rehash spikes.** An `unordered_map` that grows pays an occasional full rehash; a tree's cost per insert is steady. `reserve` removes the spikes when the final size is known. ## Common mistakes - Assuming `std::unordered_map` is always faster: for small maps, or for keys whose hash is expensive (long strings), `std::map` or even a sorted vector can win; measure. - Assuming O(1) is guaranteed: the standard states it as an average and gives `size()` as the worst case. - Expecting `std::map`-style iterator stability: every insert into an `unordered_map` may invalidate all iterators, although references to elements survive.

  • Why does std::unordered_map<std::pair<int, int>, int> fail to compile while std::map<std::pair<int, int>, int> works?
    `std::map` needs only `operator<`, which `std::pair` provides lexicographically. `std::unordered_map` needs `std::hash<std::pair<int, int>>`, and the standard library provides no hash for pairs or tuples, so that specialization is disabled and the container cannot be instantiated. Supply a hasher type as the third template argument that combines the two members.
  • Is it safe to compare two std::unordered_map objects with operator== if they were filled in different orders?
    Yes. Equality of unordered containers is defined element-wise regardless of order: same size, and each key's equivalent group in one container is a permutation of the other's. It costs O(n) on average and O(n^2) worst case, and it is only defined if both containers use equality predicates that behave the same.

  • std::unordered_map lookups are guaranteed O(1) in every case
  • std::unordered_map iterates in insertion order
  • std::pair keys work in std::unordered_map without a custom hash
  • std::unordered_map is always faster than std::map
  • std::unordered_map needs operator< on the key type
open as a page

How do you make a struct holding a user id and a device id usable as a std::unordered_map key in C++?

level: middleimportance: must knowfreq 65%

basics

~20 s

Give the struct equality, such as a defaulted operator== in C++20, and a hash: specialize std::hash for it or pass a hasher type as the third template argument. Keys that compare equal must hash equal, and the hash should mix every field.

open as a page

What do load_factor, max_load_factor, rehash and reserve mean for a C++ std::unordered_map, and when should you call reserve?

level: middleimportance: should knowfreq 50%

basics

~20 s

load_factor() is size() divided by bucket_count(); when an insert would exceed max_load_factor(), 1.0 by default, the table rehashes into more buckets. rehash(n) asks for at least n buckets; reserve(n) makes room for n elements. Reserve before a known bulk insert.

open as a page

A session cache std::unordered_map keyed by user id and device id slows down under load although load_factor() looks normal; how do you diagnose and fix it?

level: seniorimportance: should knowfreq 40%

basics

~20 s

Suspect the hash, not the table size: load_factor() is an average that hides one overloaded bucket. Measure bucket_size(bucket(key)) and the largest bucket, then replace a weak combine such as user ^ device with one that mixes every field.

open as a page

Code inserts into a std::unordered_map while holding an iterator to one element and a pointer to another; which survives a rehash, and why?

level: seniorimportance: should knowfreq 45%

basics

~20 s

The pointer survives and the iterator may not. A rehash invalidates every iterator and reorders elements, but each element lives in its own node that is relinked rather than moved, so pointers and references stay valid until that element is erased.

open as a page

Should a team standardize on std::unordered_map or a third-party open-addressing hash map for hot lookup paths, and how would you decide?

level: principalimportance: should knowfreq 30%

basics

~20 s

Keep std::unordered_map as the default where code relies on stable references, node handles or the bucket interface; adopt an open-addressing library behind a project alias only where profiles show hash lookups hot, after benchmarking real keys and auditing reference-stability assumptions.

open as a page