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.

C++

#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";
}

Output

Ada -> Eng
Bo -> Ops
Cy -> Eng
probes=4 nested-loop comparisons=8

Explanation

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.

Explore the dry run

Guided walkthroughReady

1#include <iostream>

2#include <string>

3#include <unordered_map>

4#include <vector>

6struct Employee {

7 std::string name;

8 int dept;

9};

11int main() {

12 std::unordered_map<int, std::string> departments = {{1, "Eng"}, {2, "Ops"}};

13 std::vector<Employee> staff = {{"Ada", 1}, {"Bo", 2}, {"Cy", 1}, {"Di", 3}};

15 int probes = 0;

16 for (const Employee& e : staff) {

17 ++probes;

18 auto it = departments.find(e.dept);

19 if (it != departments.end()) {

20 std::cout << e.name << " -> " << it->second << "\n";

21 }

22 }

23 std::cout << "probes=" << probes << " nested-loop comparisons="

24 << staff.size() * departments.size() << "\n";

25}

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

Prepared trace of the published program. Some rows group repeated iterations.
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

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.

C++: a hash join with unordered_map

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading