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
- First repeated letter in a word.
- Sorted word count: count with an
unordered_map(fast), then print alphabetically. - Chessboard: store the squares a rook attacks in an
unordered_set<pair<int,int>>with your own hash. - 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
- How does
unordered_mapwork inside? A hash table: an array of buckets; hash(key) % bucket_count picks the bucket; colliding keys share a bucket's chain (separate chaining). - Average and worst-case complexity of
find? O(1) average, O(n) worst case (everything in one bucket). - 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. - Why does
unordered_map<pair<int,int>, int>not compile? There is nostd::hash<pair<int,int>>; supply your own hash type (and keys need==). maporunordered_map? Need order, ranges or guaranteed O(log n):map. Need fast lookups and no order:unordered_map.- What makes a good hash function? Deterministic, fast, and it spreads different keys over different buckets.
- Solve Two Sum in O(n). Walk once with an
unordered_set(or a map from value to index): for each x, check whethertarget - xwas seen. - What does
reservedo 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
mapstill 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_setwork likemap/set, but have no order and nolower_bound.- Collisions share a bucket's chain; the load factor is kept under 1 by rehashing;
reserveplans ahead. - A
pairor your own struct as a key needs your own hash (a struct withoperator()) and==. unordered_setanswers "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.