C++: a hash join with unordered_map
Join two tables by building a hash table on one and probing it with each row of the other.
On this page
C++ structs, vectors, and unordered_map.
- Join two tables by building a hash table on one and probing it with each row of the other.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
A join combines rows from two tables whose key columns match. A nested-loop join compares every pair of rows. A hash join builds an unordered_map from the join key of the smaller table and then probes it once per row of the other table, so the work is proportional to the sizes of the two tables added together.
find returns an iterator to the entry or end if the key is missing. A row with no match is dropped, as in an inner join. This is the same strategy a database engine chooses when it has no useful index on the join column.
Code example
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
struct Employee {
std::string name;
int dept;
};
int main() {
std::unordered_map<int, std::string> departments = {{1, "Eng"}, {2, "Ops"}};
std::vector<Employee> staff = {{"Ada", 1}, {"Bo", 2}, {"Cy", 1}, {"Di", 3}};
int probes = 0;
for (const Employee& e : staff) {
++probes;
auto it = departments.find(e.dept);
if (it != departments.end()) {
std::cout << e.name << " -> " << it->second << "\n";
}
}
std::cout << "probes=" << probes << " nested-loop comparisons="
<< staff.size() * departments.size() << "\n";
}Ada -> Eng Bo -> Ops Cy -> Eng probes=4 nested-loop comparisons=8
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
#include <iostream>#include <string>#include <unordered_map>#include <vector> struct Employee { std::string name; int dept;}; int main() { std::unordered_map<int, std::string> departments = {{1, "Eng"}, {2, "Ops"}}; std::vector<Employee> staff = {{"Ada", 1}, {"Bo", 2}, {"Cy", 1}, {"Di", 3}}; int probes = 0; for (const Employee& e : staff) { ++probes; auto it = departments.find(e.dept); if (it != departments.end()) { std::cout << e.name << " -> " << it->second << "\n"; } } std::cout << "probes=" << probes << " nested-loop comparisons=" << staff.size() * departments.size() << "\n";}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Build phase: department id maps to title. | departments = {1: Eng, 2: Ops} | — | |
| Probe phase: one average O(1) lookup per employee. | Di has dept 3, so find returns end() | — | |
| Matching rows are written out; Di is skipped. | Di has dept 3, so find returns end() | Ada -> Eng Bo -> Ops Cy -> Eng | |
| Four lookups replaced eight pair comparisons. | Di has dept 3, so find returns end() | Ada -> Eng Bo -> Ops Cy -> Eng probes=4 nested-loop comparisons=8 |
Behind the scenes
How C++ processes this code
The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.
Cost and common mistakes
Average O(n + m) time and O(m) space, against O(n·m) for a nested loop.
- operator[] on a map inserts a default entry for a missing key. Use find to probe without changing the table.
- Only equality joins work this way. Range conditions need a sorted structure.
Try it yourself
What if two departments shared the same id?
Reveal answer and reasoning
unordered_map keeps one value per key, so a duplicate key would be rejected by insert. Use unordered_multimap to keep both.