Java · Course navigation

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.

On this page

Before you start

Java HashMap and for-each loops.

Join two collections by building a hash table on one side and probing it with the other.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

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.