C++: a hash join with unordered_map
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.
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";
}