SyntaxPilot
Courses/C++/Lesson 24

C++ · Lesson 24 of 40 · 10 min

STL 4: unordered_map and unordered_set

queued

These are the notes for C++ episode 24, the fourth STL episode. In episode 23 you invented the balanced search tree, and std::map found a key in about log₂ n steps. Here you go one better: you let the key itself say where it lives. You will invent hashing and the hash table, and meet std::unordered_map and std::unordered_set. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; outputs and error messages are copied from those runs. Timings change from run to run and machine to machine; compare the ratios. The giant hash numbers can also differ between compilers.

The problem: duplicate UPI payments

You scan a QR code and tap Pay; every payment gets a transaction ID. The network blinks and your app sends the same payment again, with the same ID. So for every payment the bank asks: have I seen this ID before? If yes, don't charge twice. On a festival sale day that is a million payments a minute.

Step 1: the tool we know, a map

#include <iostream>
#include <map>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    auto start = steady_clock::now();
    map<int, int> paid;                     // transaction ID -> amount
    for (int id = 0; id < 1000000; id++)
        paid[id * 7] = 100;
    int seen = 0;
    for (int id = 0; id < 1000000; id++)    // "seen before?"
        seen += paid.count(id * 7);
    auto end = steady_clock::now();
    cout << "map: " << seen << " checks in "
         << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
    return 0;
}

Output:

map: 1000000 checks in 422 ms

A million checks in a few hundred milliseconds. Not bad, but it is one minute's traffic on one server.

Why it's still not enough

  • With a million keys, every lookup walks about 20 levels down the tree (log₂ 1000000 ≈ 20).
  • Each level is a different node somewhere else in memory. Jumping around memory (pointer chasing) is slow for the CPU, which is fastest when data sits side by side.
  • We are still searching, just searching smarter. What if we didn't search at all?

Step 2: the hostel warden's trick

A big hostel. When you join, the warden doesn't search the register for a free room. She takes your roll number, 2317, and does a quick sum: the last two digits. Room 17. Later, where is student 2317? Don't open any register: do the same sum, walk to room 17. One step, however big the hostel.

At the hostel In C++
roll number the key
the warden's rule (last two digits) a hash function: key → a number
the rooms buckets
room = rule(roll) bucket = hash(key) % bucket_count
walk straight to the room lookup in O(1) on average (constant time)
  • A hash function turns a key into a number (its hash). It must be deterministic: the same key always gives the same number, or you could never find Ravi again.
  • % (remainder) squeezes that number into a bucket index from 0 to bucket_count − 1.
  • O(1), constant time: the work doesn't grow with the number of keys.

Step 3: std::hash, C++'s built-in hash functions

C++ has std::hash<T> for every basic type (int, char, double, string, pointers...), in <functional>. You create one, then call it like a function:

#include <iostream>
#include <string>
#include <functional>
using namespace std;

int main() {
    hash<string> h;                // the hash function for strings
    cout << h("Ravi") << endl;
    cout << h("Ravi") << endl;     // same key, same number
    cout << h("Asha") << endl;
    cout << "Ravi goes to bucket " << h("Ravi") % 8 << endl;
    cout << "Asha goes to bucket " << h("Asha") % 8 << endl;
    return 0;
}

Output:

12332650391072172998
12332650391072172998
14913097004995893208
Ravi goes to bucket 6
Asha goes to bucket 0

Ravi gives the same huge number both times; % 8 turns it into a bucket from 0 to 7. That is the whole trick of a hash table.

Step 4: unordered_map

#include <unordered_map>. Same interface as map:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, string> phone;
    phone["Ravi"] = "98100 22222";
    phone["Asha"] = "98100 11111";
    phone["Meena"] = "98100 33333";
    phone["Zoya"] = "98100 44444";
    cout << "Ravi: " << phone["Ravi"] << endl;
    if (phone.count("Kiran") == 0) cout << "Kiran: not found" << endl;
    for (auto p : phone)                 // no order promised
        cout << p.first << " -> " << p.second << endl;
    return 0;
}

Output:

Ravi: 98100 22222
Kiran: not found
Zoya -> 98100 44444
Meena -> 98100 33333
Asha -> 98100 11111
Ravi -> 98100 22222

The answers are the same as a map's, but look at the order: not A to Z, not the order we added them. It's the order of the buckets. There's no tree, so there's no order: "unordered" is in the name.

Works the same as map Not available
[] (and its trap: a missing key is added), at, count, find, insert, erase, size, empty, range-for lower_bound, upper_bound, sorted iteration, begin() = smallest key

The race

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    auto start = steady_clock::now();
    map<int, int> m;
    for (int id = 0; id < 1000000; id++) m[id * 7] = 100;
    int a = 0;
    for (int id = 0; id < 1000000; id++) a += m.count(id * 7);
    auto end = steady_clock::now();
    cout << "map:           " << duration_cast<milliseconds>(end - start).count() << " ms" << endl;

    start = steady_clock::now();
    unordered_map<int, int> u;
    for (int id = 0; id < 1000000; id++) u[id * 7] = 100;
    int b = 0;
    for (int id = 0; id < 1000000; id++) b += u.count(id * 7);
    end = steady_clock::now();
    cout << "unordered_map: " << duration_cast<milliseconds>(end - start).count() << " ms" << endl;
    return 0;
}

Output:

map:           241 ms
unordered_map: 77 ms

The same work, several times faster. Compute the bucket, look there; no walk down a tree.

Step 5: collisions, load factor and rehash

Students 2317 and 4517 both end in 17: two keys, one bucket. That's a collision. It's normal: room 17 simply holds both, and a lookup checks the few names inside. In std::unordered_map, each bucket holds a short chain of entries (a linked list, as in episode 22). This is called separate chaining.

As the hostel fills, rooms get crowded and every visit checks more names. The average number of entries per bucket is the load factor = size / bucket_count. When it passes max_load_factor() (1.0 by default), C++ builds a bigger table (more buckets) and moves every entry once: a rehash. It costs a moment, but it keeps every chain short. reserve(n) makes room for n entries up front, so no rehash happens on the way.

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, int> rooms;
    for (int roll = 1; roll <= 100; roll++) {
        rooms[roll] = roll;
        if (roll == 10 || roll == 50 || roll == 100)
            cout << rooms.size() << " students, "
                 << rooms.bucket_count() << " buckets, load "
                 << rooms.load_factor() << endl;
    }
    rooms.reserve(1000000);          // build a big hostel up front
    cout << "After reserve: " << rooms.bucket_count() << " buckets" << endl;
    return 0;
}

Output:

10 students, 13 buckets, load 0.769231
50 students, 59 buckets, load 0.847458
100 students, 127 buckets, load 0.787402
After reserve: 1056323 buckets

The bucket count jumps (13 → 59 → 127: libstdc++ uses prime numbers of buckets) and the load factor stays under 1. Those jumps are rehashes.

Member What it tells you or does
bucket_count() how many buckets there are now
load_factor() size / bucket_count
max_load_factor() the limit that triggers a rehash (1.0 by default)
bucket(key) which bucket that key is in
rehash(n) at least n buckets
reserve(n) enough buckets for n elements without passing the max load factor

Step 6: a key C++ can't hash

A cinema booking: a seat is a row and a seat number, so the key is a pair<int, int>.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<pair<int, int>, string> seat;   // (row, seat) -> name
    seat[{3, 4}] = "Ravi";
    cout << seat[{3, 4}] << endl;
    return 0;
}

g++ says:

main.cpp:7:43: error: use of deleted function ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = std::__cxx11::basic_string<char>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::__cxx11::basic_string<char> > >]’
/usr/include/c++/13/bits/unordered_map.h:148:7: error: use of deleted function ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::__cxx11::basic_string<char> > >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’
/usr/include/c++/13/bits/hashtable.h:530:7: error: use of deleted function ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, std::__cxx11::basic_string<char> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’

The key line is use of deleted function. Read inside the brackets: _Hash = std::hash<std::pair<int, int> >. That hash doesn't exist: C++ has no std::hash for a pair (or for your own structs). Note that a normal map<pair<int, int>, string> compiles fine: a tree only needs <, and pairs can be compared. A hash table needs a hash function.

Writing your own hash

A hash function in C++ is a function object: a struct with an operator() that takes a key and returns a size_t (an unsigned whole number type used for sizes). Pass it as the third template argument:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

struct SeatHash {                  // our own hash function
    size_t operator()(const pair<int, int>& s) const {
        return s.first * 1000 + s.second;   // row 3, seat 4 -> 3004
    }
};

int main() {
    unordered_map<pair<int, int>, string, SeatHash> seat;
    seat[{3, 4}] = "Ravi";
    seat[{3, 5}] = "Asha";
    cout << "Row 3, seat 4: " << seat[{3, 4}] << endl;
    cout << "Row 3, seat 5: " << seat[{3, 5}] << endl;
    cout << "Row 9, seat 1 booked? " << seat.count({9, 1}) << endl;
    return 0;
}

Output:

Row 3, seat 4: Ravi
Row 3, seat 5: Asha
Row 9, seat 1 booked? 0

A good hash gives different keys different numbers as often as possible. Ours is perfect while a row has fewer than 1000 seats.

Your own struct as a key

A struct key needs two things: a hash, and == (to tell two keys in the same bucket apart). A common way to combine two hashes is to mix them, for example with ^ (XOR) and a multiplication:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

struct Student {
    string name;
    int roll;
    bool operator==(const Student& o) const { return name == o.name && roll == o.roll; }
};

struct StudentHash {
    size_t operator()(const Student& s) const {
        size_t h1 = hash<string>()(s.name);
        size_t h2 = hash<int>()(s.roll);
        return h1 ^ (h2 * 31);            // mix the two hashes
    }
};

int main() {
    unordered_map<Student, int, StudentHash> marks;
    marks[{"Ravi", 17}] = 91;
    marks[{"Asha", 4}] = 88;
    cout << "Ravi (17): " << marks[{"Ravi", 17}] << endl;
    cout << "Ravi (18) stored? " << marks.count({"Ravi", 18}) << endl;
    return 0;
}

Output:

Ravi (17): 91
Ravi (18) stored? 0

Step 7: unordered_set, "seen before?"

For duplicate payments we only need keys: #include <unordered_set>. insert(x) returns a pair<iterator, bool>; .second is true if x was new.

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    vector<long long> ids = {41001, 41002, 41003, 41002, 41004, 41001};
    unordered_set<long long> seen;
    for (long long id : ids) {
        if (seen.insert(id).second)        // true: it was new
            cout << "Pay " << id << endl;
        else
            cout << "Duplicate " << id << ": blocked" << endl;
    }
    cout << seen.size() << " real payments" << endl;
    return 0;
}

Output:

Pay 41001
Pay 41002
Pay 41003
Duplicate 41002: blocked
Pay 41004
Duplicate 41001: blocked
4 real payments

41002 and 41001 came twice and the second time each was blocked. Nobody was charged twice.

Step 8: the two sum pattern

You have ₹500 for two gifts and a list of prices. Which two add up to exactly 500? The obvious way checks every pair: n × n / 2 checks, slow for a big list. Better: walk the list once, remembering every price you've passed in a set. For each price p, its partner is budget - p. Did we already pass the partner? One O(1) lookup.

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    vector<int> prices = {120, 450, 300, 200, 380};
    int budget = 500;
    unordered_set<int> seen;                 // prices we have passed
    for (int p : prices) {
        if (seen.count(budget - p))          // its partner came before?
            cout << budget - p << " + " << p << " = " << budget << endl;
        seen.insert(p);
    }
    return 0;
}

Output:

300 + 200 = 500
120 + 380 = 500

This is Two Sum, one of the most asked interview questions. O(n) time instead of O(n²), at the cost of O(n) extra memory.

map vs unordered_map

map / set unordered_map / unordered_set
Built on balanced binary search tree (red-black) hash table (buckets + chains)
find / insert / erase O(log n), always O(1) on average, O(n) worst case
Order sorted by key none (bucket order)
lower_bound, ranges yes no
A custom key needs operator< a hash function and operator==
Pick it when you need order, ranges or a guaranteed bound you need raw speed for lookups

The worst case

If every key lands in the same bucket, a lookup walks one long chain: O(n). A bad hash does that, and so can keys deliberately chosen to collide (an attacker feeding a server crafted input). The tree never has a bad day.

#include <iostream>
#include <unordered_set>
#include <chrono>
using namespace std;
using namespace std::chrono;

struct LazyHash {                         // every key -> bucket of 0
    size_t operator()(int x) const { return 0; }
};

int main() {
    auto start = steady_clock::now();
    unordered_set<int> good;
    for (int i = 0; i < 20000; i++) good.insert(i);
    auto mid = steady_clock::now();
    unordered_set<int, LazyHash> lazy;
    for (int i = 0; i < 20000; i++) lazy.insert(i);
    auto end = steady_clock::now();
    cout << "good hash: " << duration_cast<milliseconds>(mid - start).count() << " ms" << endl;
    cout << "lazy hash: " << duration_cast<milliseconds>(end - mid).count() << " ms" << endl;
    return 0;
}

Output:

good hash: 1 ms
lazy hash: 902 ms

Common mistakes (and the real g++ messages)

Mistake What happens Fix
unordered_map<pair<int,int>, string> m; error: use of deleted function ‘std::unordered_map<...>::unordered_map() [with _Key = std::pair<int, int>; ... _Hash = std::hash<std::pair<int, int> >; ...]’ write a hash struct, pass it as the 3rd type
Expecting sorted output compiles; prints in bucket order use map, or copy into a map / sort a vector at the end
u.lower_bound(10) error: ‘class std::unordered_map<int, int>’ has no member named ‘lower_bound’ ranges need a tree: map / set
A lazy hash (return 0;) compiles and runs, but every key collides: O(n) per lookup (900 ms vs 1 ms above) spread keys out
Struct key with a hash but no == compile error about operator== / std::equal_to add bool operator==(const T&) const
Reading with u[key] silently adds the key, like map count, find or at

Here is the lower_bound error, for real:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, int> u = {{10, 1}, {20, 2}};
    auto it = u.lower_bound(10);
    return 0;
}

g++ says:

main.cpp:7:17: error: ‘class std::unordered_map<int, int>’ has no member named ‘lower_bound’

Mini project: an OTP checker

Commands: send <phone> <otp> stores the latest OTP for a phone; check <phone> <otp> verifies it, and a verified OTP can be used only once.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, string> otp;        // phone -> latest OTP
    string cmd, phone, code;
    while (cin >> cmd && cmd != "end") {
        if (cmd == "send") {
            cin >> phone >> code;
            otp[phone] = code;                 // a new OTP replaces the old one
            cout << "OTP sent to " << phone << endl;
        } else if (cmd == "check") {
            cin >> phone >> code;
            auto it = otp.find(phone);
            if (it == otp.end()) cout << phone << ": no OTP sent" << endl;
            else if (it->second != code) cout << phone << ": wrong OTP" << endl;
            else { cout << phone << ": verified" << endl; otp.erase(it); }   // one use only
        }
    }
    return 0;
}

Output:

OTP sent to 98100
OTP sent to 98200
98100: wrong OTP
98100: verified
98100: no OTP sent
99999: no OTP sent

(Input typed into the program's input box: send 98100 4821, send 98200 1177, check 98100 1111, check 98100 4821, check 98100 4821, check 99999 0000, end.)

Extensions: allow only 3 wrong tries per phone (a second unordered_map<string, int> for the count).

Practice

  1. First repeated letter in a word.
  2. Sorted word count: count with an unordered_map (fast), then print alphabetically.
  3. Chessboard: store the squares a rook attacks in an unordered_set<pair<int,int>> with your own hash.
  4. Timing with reserve: insert 2 million keys with and without reserve.
Solutions

1.

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    string word = "programming";
    unordered_set<char> seen;
    for (char c : word) {
        if (!seen.insert(c).second) {
            cout << "First repeated letter: " << c << endl;
            break;
        }
    }
    return 0;
}

Output:

First repeated letter: r

2. Count in the hash table, then copy into a map once, which sorts it.

#include <iostream>
#include <unordered_map>
#include <map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    stringstream in("chai coffee chai lassi chai coffee");
    unordered_map<string, int> freq;
    string w;
    while (in >> w) freq[w]++;                          // fast counting
    map<string, int> sorted(freq.begin(), freq.end());  // sort once at the end
    for (auto p : sorted) cout << p.first << ": " << p.second << endl;
    return 0;
}

Output:

chai: 3
coffee: 2
lassi: 1

3. row * 8 + col gives each of the 64 squares its own number from 0 to 63: a perfect hash, no collisions at all.

#include <iostream>
#include <unordered_set>
#include <utility>
using namespace std;

struct SquareHash {
    size_t operator()(const pair<int, int>& s) const { return s.first * 8 + s.second; }   // 0..63, no collisions
};

int main() {
    unordered_set<pair<int, int>, SquareHash> attacked;
    int r = 4, c = 4;                       // a rook on row 4, column 4
    for (int i = 0; i < 8; i++) {
        if (i != c) attacked.insert({r, i});
        if (i != r) attacked.insert({i, c});
    }
    cout << "Squares attacked: " << attacked.size() << endl;
    cout << "(4, 7) attacked? " << attacked.count({4, 7}) << endl;
    cout << "(5, 6) attacked? " << attacked.count({5, 6}) << endl;
    return 0;
}

Output:

Squares attacked: 14
(4, 7) attacked? 1
(5, 6) attacked? 0

4. reserve skips every rehash on the way.

#include <iostream>
#include <unordered_map>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    auto start = steady_clock::now();
    unordered_map<int, int> a;
    for (int i = 0; i < 2000000; i++) a[i] = i;
    auto mid = steady_clock::now();
    unordered_map<int, int> b;
    b.reserve(2000000);                       // all buckets up front
    for (int i = 0; i < 2000000; i++) b[i] = i;
    auto end = steady_clock::now();
    cout << "no reserve: " << duration_cast<milliseconds>(mid - start).count() << " ms" << endl;
    cout << "reserve:    " << duration_cast<milliseconds>(end - mid).count() << " ms" << endl;
    return 0;
}

Output:

no reserve: 98 ms
reserve:    124 ms

Quick quiz

What does this print?

unordered_set<int> s = {5, 1, 5, 3, 1};
s.insert(3);
cout << s.size() << " " << s.count(5)
     << " " << s.count(7);
Answer

3 1 0. A set keeps each value once, so {5, 1, 5, 3, 1} holds 5, 1 and 3. Inserting 3 again does nothing. count is only ever 0 or 1 in a set.

Interview questions

  1. How does unordered_map work inside? A hash table: an array of buckets; hash(key) % bucket_count picks the bucket; colliding keys share a bucket's chain (separate chaining).
  2. Average and worst-case complexity of find? O(1) average, O(n) worst case (everything in one bucket).
  3. What is the load factor, and what happens when it gets too big? size / bucket_count. Past max_load_factor() (1.0) the table rehashes into more buckets.
  4. Why does unordered_map<pair<int,int>, int> not compile? There is no std::hash<pair<int,int>>; supply your own hash type (and keys need ==).
  5. map or unordered_map? Need order, ranges or guaranteed O(log n): map. Need fast lookups and no order: unordered_map.
  6. What makes a good hash function? Deterministic, fast, and it spreads different keys over different buckets.
  7. Solve Two Sum in O(n). Walk once with an unordered_set (or a map from value to index): for each x, check whether target - x was seen.
  8. What does reserve do and why use it? Allocates enough buckets for n elements, avoiding repeated rehashes while inserting.

Glossary

Term Meaning, with an example
hashing Turning a key into a number that says where to store it.
hash function The rule key → number; it must give the same number for the same key: hash<string>()("Ravi").
hash (value) The number a hash function returns for a key.
std::hash<T> C++'s built-in hash function for basic types, in <functional>.
hash table An array of buckets where a key's bucket is computed from its hash.
bucket One slot of a hash table; it holds the entries whose keys land there.
collision Two different keys landing in the same bucket: rolls 2317 and 4517 → room 17.
separate chaining Handling collisions by keeping a small list of entries in each bucket.
load factor Entries per bucket on average: size / bucket_count.
rehash Building a bigger bucket array and moving every entry into it.
reserve(n) Prepare enough buckets for n entries up front.
O(1), constant time Work that does not grow with the number of elements.
average vs worst case Typical cost over normal inputs vs the most expensive possible input.
unordered_map Hash table of key → value pairs; no order.
unordered_set Hash table of unique keys; no order.
function object (functor) A struct with operator(), so an object can be called like a function: SeatHash{}({3, 4}).
size_t An unsigned whole-number type used for sizes and hash values.
XOR (^) Bitwise "exclusive or", often used to mix two hash values.
deterministic Always gives the same output for the same input.
pointer chasing Following links from node to node scattered in memory; slower than reading memory in a row.
Two Sum The classic problem: find two numbers in a list that add up to a target.
use of deleted function g++'s message when code needs a function that was deliberately removed, such as a hash table constructor with no usable hash.

Summary

  • A map still searches: about 20 steps per lookup for a million keys, each a jump in memory.
  • A hash function turns a key into a number; number % bucket_count picks the bucket. Lookups take about one step, O(1) on average.
  • unordered_map / unordered_set work like map / set, but have no order and no lower_bound.
  • Collisions share a bucket's chain; the load factor is kept under 1 by rehashing; reserve plans ahead.
  • A pair or your own struct as a key needs your own hash (a struct with operator()) and ==.
  • unordered_set answers "seen before?", the heart of duplicate detection and Two Sum.
  • Worst case is O(n) if everything collides; need order or a guarantee, use map.

Next episode: sometimes you don't need to find anything. You need the last thing you did (undo), the first person in line, or the most urgent patient: stack, queue and priority_queue.