Skip to content
Tutorials Center
My learning

Topics

Lesson 100 of 171 ยท The Standard Library (STL)

std::unordered_map

Learn C++ std::unordered_map - how hash tables give average O(1) lookups, buckets and load factor, reserve and rehash, custom hash functions and counting words.

std::unordered_map<Key, T> (header <unordered_map>) stores key-value pairs in a hash table. Where std::map keeps its keys sorted in a tree and needs about logโ‚‚ n comparisons per lookup, an unordered map computes a hash of the key, jumps straight to a small group of candidates, and usually finds the element after one or two comparisons. On average, insertion, lookup and erasure are O(1), no matter how many elements it holds.

The price is that the elements have no meaningful order, and performance depends on a good hash function. In this lesson you'll learn the interface (mostly the same as std::map), how buckets and the load factor work, why reserve matters, how to hash your own types, what happens with a bad hash, and when the ordered map is still the better choice. Along the way you'll build the classic first program for a hash map: a word counter.

The interface: almost identical to std::map

If you know std::map, you already know most of std::unordered_map:

  • m[key] inserts a value-initialized element if the key is missing (the same pitfall as with map), and is perfect for counting.
  • insert, insert_or_assign, try_emplace and emplace behave exactly as described in the std::map lesson.
  • find, contains (C++20), count and at look up without inserting.
  • erase(key), erase(it) and std::erase_if(m, pred) remove elements.
  • Elements are std::pair<const Key, T>, and structured bindings unpack them.

What's missing: lower_bound, upper_bound and anything else that relies on order. Iteration visits elements in an unspecified order that can change whenever the table grows.

C++ Counting words with unordered_map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Copying the entries into a vector and sorting is the standard way to present hash-map contents in a defined order. Ties are broken alphabetically, so the output is deterministic. The Text Statistics project builds this idea into a full program.

How a hash table works

An unordered map owns an array of buckets. To find where a key belongs, it:

  1. Calls the hash function, std::hash<Key>{}(key), which returns a std::size_t.
  2. Reduces the hash to a bucket index (GCC's library uses hash % bucket_count(), with a prime number of buckets).
  3. Searches that bucket's elements, comparing keys with operator== (or the equality predicate you supply).

Different keys can land in the same bucket: a collision. The standard containers handle collisions with chaining: each bucket refers to a linked list of nodes. As long as the hash spreads keys evenly, every bucket holds about one element and step 3 is nearly free.

Load factor and rehashing

The load factor is size() / bucket_count(), the average number of elements per bucket. When an insertion would push it above max_load_factor() (1.0 by default), the table rehashes: it allocates a bigger bucket array (roughly double) and relinks every node into its new bucket. Like vector growth, this makes insertion amortized O(1).

C++ Buckets, load factor and reserve

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Without reserve, the map rehashed eight times on the way to 2,000 elements; each rehash touches every element. With reserve(n) (which means "make room for n elements", unlike rehash(n), which asks for at least n buckets), it never rehashes. The exact bucket counts are an implementation detail: GCC uses primes, other libraries use powers of two.

You can trade memory for speed by lowering the maximum load factor, m.max_load_factor(0.5f), so buckets stay emptier. Raising it saves memory but lengthens the chains.

Iterator invalidation

A rehash invalidates all iterators, but not references or pointers to elements: the nodes themselves never move, only the bucket array changes. Erasing invalidates only the erased element. So holding T& references into an unordered map across insertions is safe, but holding iterators is not (unless you reserve first and stay below the limit).

Hashing your own types

std::hash is specialized for the built-in arithmetic types, pointers, std::string, std::string_view, smart pointers, std::optional, std::variant and a few others. It is not specialized for std::pair, std::tuple or your own structs, so std::unordered_map<std::pair<int, int>, T> doesn't compile out of the box.

To use a custom key, you need two things that agree with each other:

  • Equality: operator== (often = default since C++20) or a custom equality functor.
  • A hash: either a specialization of std::hash<Key>, or a hasher type passed as the third template argument.

The golden rule: if a == b, then hash(a) == hash(b). The reverse need not hold (that's a collision), but breaking the rule makes equal keys land in different buckets, so lookups fail randomly.

C++ A custom hash for a struct key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Simply XOR-ing the member hashes (hash(x) ^ hash(y)) is a common but poor choice: it maps (1, 2) and (2, 1) to the same value, and every (n, n) to 0. The combining step above shifts and mixes bits so that order matters and patterns spread out. Note that GCC's std::hash<int> is the identity function, which is fine for prime bucket counts but shows why mixing matters.

Keys that make poor hash keys

  • Floating-point numbers: 0.1 + 0.2 and 0.3 are different keys, and NaN is never equal to itself, so a NaN key can be inserted repeatedly and never found.
  • Pointers: they hash the address, not the pointee. Two equal strings at different addresses are different keys.
  • Mutable keys: keys are const inside the map; if a key's hash depends on something that changes elsewhere (through a pointer), the element is lost in the wrong bucket.

What a bad hash costs

All of the O(1) promise rests on the hash spreading keys evenly. With a hash that sends every key to the same bucket, the table degrades into one long linked list: each insertion and lookup scans every element, so n insertions cost O(nยฒ).

C++ Good hash versus terrible hash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The exact times vary, but the terrible hash is typically a hundred or more times slower, and the gap grows with n. This isn't just a theoretical worry: if an attacker can choose your keys (say, field names in a web request) and knows your hash function, they can craft collisions to slow your server to a crawl. That's called hash flooding; servers that face untrusted input use randomized or keyed hashes for this reason.

Heterogeneous lookup

Looking up a std::string key with a std::string_view or a literal normally creates a temporary std::string. Since C++20, unordered containers support transparent lookup, like std::map with std::less<>. Both the hasher and the equality type must declare is_transparent:

C++ Looking up string keys without allocating

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::hash<std::string_view> produces the same value as std::hash<std::string> for the same characters, which is what makes this safe. In hot code that looks up many keys from parsed text, this avoids an allocation per lookup for long keys.

unordered_map or map?

std::unordered_map std::map
Lookup, insert, erase O(1) average, O(n) worst O(log n) guaranteed
Iteration order Unspecified, changes on rehash Sorted by key
Range queries, nearest key No lower_bound, upper_bound
Key requirements Hash + equality Less-than ordering
Memory Nodes + bucket array Nodes with 3 pointers each

Default to unordered_map for pure lookup tables (caches, indexes, counting) with keys that hash well, such as integers and strings. Choose std::map when you need sorted output, range queries, guaranteed worst-case time, or keys that are easy to order but awkward to hash. And as with every container: when it really matters, measure. The standard hash maps are reliable but not the fastest possible design (every element is a separate node), which is why high-performance projects sometimes use open-addressing tables from libraries.

std::unordered_multimap also exists, allowing duplicate keys, with equal_range and count like std::multimap.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the average time complexity of find on a std::unordered_map with a good hash function?

    The hash leads straight to one bucket, which holds about one element on average, so lookups are O(1) on average. A bad hash degrades them to O(n).
  2. 2. std::unordered_map<std::pair<int, int>, int> m; Why doesn't this compile?

    std::pair has operator== but no standard hash. Pass a hasher type as the third template argument or specialize std::hash for your own key type.
  3. 3. After many insertions cause a rehash, which of these is still valid?

    Rehashing rebuilds the bucket array but doesn't move the nodes, so references and pointers to elements stay valid. Iterators are invalidated and the order may change.
  4. 4. A custom hash returns the same value for every key. What happens?

    Correctness only needs equal keys to have equal hashes. A constant hash satisfies that, but every lookup has to scan one long chain.
  5. 5. You need to print the entries of a map in key order and find all keys between 100 and 200. Which container fits best?

    Ordered output and range queries are exactly what std::map's tree provides. An unordered_map would need a copy and a sort for every such query.

Summary

  • std::unordered_map is a hash table: average O(1) insert, find and erase; elements in no particular order, and the order can change on rehash.
  • Its interface mirrors std::map ([], try_emplace, insert_or_assign, find, contains, at, erase_if) minus the ordered operations.
  • Keys go to buckets by hash. When the load factor exceeds max_load_factor() (1.0), the table rehashes; reserve(n) avoids rehashing when you know the size.
  • Rehashing invalidates iterators but not references or pointers to elements.
  • Custom keys need equality and a hash that agree: equal keys must have equal hashes. Combine member hashes with mixing, not plain XOR.
  • A bad hash (or hash flooding) turns O(1) into O(n). Transparent hashers with std::equal_to<> allow lookups by string_view without allocation (C++20).

Next: std::set and std::unordered_set, the containers that store unique keys without values.