Java: a hash join and why it beats a nested loop

Join two collections by building a hash table on one side and probing it with the other.

Java

import java.util.*;

class Main {
  static class Employee {
    final String name;
    final int deptId;

    Employee(String name, int deptId) {
      this.name = name;
      this.deptId = deptId;
    }
  }

  public static void main(String[] args) {
    Map<Integer, String> departments = new HashMap<>();
    departments.put(1, "Eng");
    departments.put(2, "Ops");

    List<Employee> staff = List.of(
        new Employee("Ada", 1), new Employee("Bo", 2),
        new Employee("Cy", 1), new Employee("Di", 3));

    int probes = 0;
    for (Employee e : staff) {
      probes++;
      String title = departments.get(e.deptId);
      if (title != null) {
        System.out.println(e.name + " -> " + title);
      }
    }
    System.out.println("probes=" + probes + " nested-loop comparisons=" + staff.size() * departments.size());
  }
}

Output

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

Explanation

A database join pairs rows from two tables whose key columns match. The simplest method, the nested-loop join, compares every row of one table with every row of the other. A hash join builds a hash table of the smaller table's keys once and then looks each row of the other table up in it.

The program joins employees to departments on the department id. Building the table touches each department once, and each employee needs one lookup, so the work is about n + m instead of n times m. The employee whose department id has no match is dropped, as in an inner join.

Explore the dry run

Guided walkthroughReady

1import java.util.*;

3class Main {

4 static class Employee {

5 final String name;

6 final int deptId;

8 Employee(String name, int deptId) {

9 this.name = name;

10 this.deptId = deptId;

11 }

12 }

14 public static void main(String[] args) {

15 Map<Integer, String> departments = new HashMap<>();

16 departments.put(1, "Eng");

17 departments.put(2, "Ops");

19 List<Employee> staff = List.of(

20 new Employee("Ada", 1), new Employee("Bo", 2),

21 new Employee("Cy", 1), new Employee("Di", 3));

23 int probes = 0;

24 for (Employee e : staff) {

25 probes++;

26 String title = departments.get(e.deptId);

27 if (title != null) {

28 System.out.println(e.name + " -> " + title);

29 }

30 }

31 System.out.println("probes=" + probes + " nested-loop comparisons=" + staff.size() * departments.size());

32 }

33}

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: the hash table maps each department id to its title.	`departments = {1=Eng, 2=Ops}`	—
Probe phase: one hash lookup per employee instead of scanning every department.	`Di has deptId 3, so title is null`	—
Only employees with a matching department are joined.	`Di has deptId 3, so title is null`	Ada -> Eng Bo -> Ops Cy -> Eng
Four lookups replaced eight comparisons.	`Di has deptId 3, so title is null`	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 for the hash table, against O(n·m) for a nested loop.

A hash join only supports equality conditions. A condition such as a.x < b.y needs another method.
Real databases choose among nested-loop, hash, and sort-merge joins using table statistics and available indexes.

Try it yourself

What changes if department 3 is added to the table?

Reveal answer and reasoning

Di would also be printed as 'Di -> ...' and all four employees would join.

Java: a hash join and why it beats a nested loop

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading