std::map finds a key in O(log n) by comparing its way down a tree. std::unordered_map computes where the key should be and looks there — O(1) on average.

The names are misleading. std::unordered_map is a hash table; the "unordered" part is what you give up.

Measured

#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>

template <typename F>
long long time_us(F f) {
    auto t0 = std::chrono::steady_clock::now();
    f();
    auto t1 = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
}

int main() {
    const int N = 200000;
    std::vector<int> keys(N);
    std::mt19937 gen(42);
    for (int i = 0; i < N; ++i) keys[i] = static_cast<int>(gen());

    std::map<int, int> ordered;
    std::unordered_map<int, int> hashed;

    std::cout << "insert " << N << ":\n";
    std::cout << "  map:           " << time_us([&]{ for (int k : keys) ordered[k] = k; }) << " us\n";
    std::cout << "  unordered_map: " << time_us([&]{ for (int k : keys) hashed[k] = k; }) << " us\n";

    long long found = 0;
    std::cout << "lookup " << N << ":\n";
    std::cout << "  map:           " << time_us([&]{ for (int k : keys) found += ordered.count(k); }) << " us\n";
    std::cout << "  unordered_map: " << time_us([&]{ for (int k : keys) found += hashed.count(k); }) << " us\n";
    std::cout << "  (found " << found << ")\n";

    std::cout << "\nbuckets: " << hashed.bucket_count()
              << ", load factor " << hashed.load_factor()
              << ", max load factor " << hashed.max_load_factor() << "\n";

    std::cout << "\nstd::hash samples:\n";
    std::hash<std::string> hs;
    std::cout << "  hash(\"a\")  = " << hs("a") << "\n";
    std::cout << "  hash(\"b\")  = " << hs("b") << "\n";
    std::hash<int> hi;
    std::cout << "  hash(42)   = " << hi(42) << "\n";
    return 0;
}

A representative run, compiled -O2. Timings vary; the ratios are the point:

insert 200000:
  map:           74456 us
  unordered_map: 40610 us
lookup 200000:
  map:           71748 us
  unordered_map: 13769 us
  (found 400000)

buckets: 351061, load factor 0.569684, max load factor 1

std::hash samples:
  hash("a")  = 4993892634952068459
  hash("b")  = 10838281452030117757
  hash(42)   = 42

Lookup is over 5× faster. Insert is under 2× faster, because the hash table pays for rehashing as it grows. Those ratios are typical: hashing wins clearly on lookup, less so on construction.

The last line deserves a pause. std::hash<int>(42) returns 42. libstdc++'s hash for integers is the identity function — it does nothing at all. That is not a bug; the container's modulo does the scattering. But it has a consequence, below.

How a hash table works

1. Compute hash(key) — a std::size_t.
2. Reduce it to a bucket index, roughly hash % bucket_count.
3. Look in that bucket. Usually it holds one element; compare with == to confirm.

Two keys can hash to the same bucket — a collision. libstdc++ chains them in a linked list, so a bucket with many entries degrades to a linear scan.

Load factor is size / bucket_count. When it exceeds max_load_factor (1.0 by default), the table rehashes: allocates more buckets and redistributes everything. That is O(n), and it invalidates every iterator.

The run above ended with 351,061 buckets for 200,000 elements — a load factor of 0.57. The table grew several times to get there, and reserve would have avoided all of it:

// hashed.reserve(200000);      // allocate enough buckets up front
// hashed.max_load_factor(0.7); // trade memory for fewer collisions

What you give up

| | map | unordered_map | |---|---|---| | Lookup | O(log n) | O(1) average, O(n) worst | | Iteration order | sorted by key | unspecified | | lower_bound / range queries | yes | no | | Iterators after insert | stable | invalidated on rehash | | Key requires | < | == and std::hash | | Memory | lower | higher (spare buckets) |

Three of those rows decide real cases.

No ordering, at all. Iteration order is unspecified and can differ between runs, compilers, and library versions. Code that depends on it is broken code that happens to work today. If you print a hash map's contents in a test, sort them first.

No range queries. lower_bound cannot exist without an order. If you need "all keys between X and Y", a hash table cannot help you at any price.

O(n) worst case. If every key lands in one bucket, lookup is a linear scan. With adversarial input this is a denial-of-service vector — and std::hash<int> being the identity function makes it easy: an attacker who can choose integer keys can pick multiples of your bucket count. Web servers and parsers that hash untrusted input use a randomly seeded hash for this reason.

Hashing your own type

Two things are needed: operator== and a hash function.

#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>

struct Point {
    int x;
    int y;

    bool operator==(const Point& other) const = default;   // hashing needs ==
};

// A hash function object. Combining is the part people get wrong: XOR alone
// makes hash({1,2}) equal hash({2,1}).
struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);
    }
};

struct BadHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ std::hash<int>{}(p.y);   // symmetric: collides
    }
};

int main() {
    std::unordered_set<Point, PointHash> points = {{1, 2}, {3, 4}, {1, 2}};
    std::cout << "size " << points.size() << "\n";
    std::cout << "contains (3,4): " << std::boolalpha << points.contains({3, 4}) << "\n";

    PointHash good;
    BadHash bad;
    std::cout << "good hash of (1,2) == (2,1): "
              << (good(Point{1,2}) == good(Point{2,1})) << "\n";
    std::cout << "bad  hash of (1,2) == (2,1): "
              << (bad(Point{1,2}) == bad(Point{2,1})) << "\n";
    return 0;
}

size 2
contains (3,4): true
good hash of (1,2) == (2,1): false
bad  hash of (1,2) == (2,1): true

BadHash XORs the two field hashes directly, so (1,2) and (2,1) collide — XOR is commutative. On a grid of coordinates that is roughly half your points colliding in pairs, for free. The << 1 in PointHash breaks the symmetry.

Even that is only adequate. The combiner worth copying is Boost's, which mixes far better:

// template <typename T>
// void hash_combine(std::size_t& seed, const T& value) {
//     seed ^= std::hash<T>{}(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// }
//
// std::size_t operator()(const Point& p) const {
//     std::size_t seed = 0;
//     hash_combine(seed, p.x);
//     hash_combine(seed, p.y);
//     return seed;
// }

0x9e3779b9 is derived from the golden ratio; the shifts spread bits between rounds. You are not expected to derive this — you are expected to use it rather than inventing your own.

Note that operator== and the hash must agree: if a == b, then hash(a) must equal hash(b). Breaking that means the table can hold two elements it considers equal, and lookups find the wrong one or neither. Nothing checks it.

The alternative to a separate hash type is specialising std::hash (lesson 12.4), which lets std::unordered_set<Point> work without naming the hasher:

// namespace std {
//     template <>
//     struct hash<Point> {
//         std::size_t operator()(const Point& p) const { ... }
//     };
// }

Specialising a standard template for your own type is explicitly allowed. Doing it for a type you do not own is not.

Choosing

Default to std::unordered_map when you only ever look keys up by exact value. It is faster, and lookup is the common case.

Use std::map when you need any of: sorted iteration, range queries, stable iterators, or a key type that has < but no sensible hash.

Use a sorted std::vector when the data is built once and then only read. std::lower_bound on a sorted vector beats both — contiguous memory, no per-node allocation, and O(log n) lookup. This is a genuinely underused option, and lesson 13.12 returns to it.

Try it

Checkpoint

• unordered_map/unordered_set are hash tables: O(1) average lookup, O(n) worst case.
• Measured here: lookup 5× faster than std::map, insert under 2× faster.
• Load factor is size / bucket_count; exceeding max_load_factor triggers a rehash.
• A rehash is O(n) and invalidates all iterators. reserve avoids repeated rehashing.
• Iteration order is unspecified — never depend on it, and sort before printing in tests.
• No lower_bound, no range queries, ever — those need an order.
• A key type needs both operator== and a hash, and the two must agree.
• std::hash<int> is the identity function in libstdc++ — relevant for adversarial input.
• Combining hashes with plain XOR makes (1,2) and (2,1) collide; use a proper combiner.
• Default to unordered_map for exact lookup, map for order, sorted vector for read-only data.