Java Top

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE

1. Overview

Filtering a Collection by a List is a common business logic scenario. There are plenty of ways to achieve this. However, some may lead to under-performing solutions if not done properly.

In this tutorial, we'll compare some filtering implementations and discuss their advantages and drawbacks.

2. Using a For-Each Loop

We'll begin with the most classic syntax, a for-each loop.

For this and all other examples in this article, we'll use the following class:

public class Employee {

    private Integer employeeNumber;
    private String name;
    private Integer departmentId;
    //Standard constructor, getters and setters.
}

We'll also use the following methods for all examples, for simplicity's sake:

private List<Employee> buildEmployeeList() {
    return Arrays.asList(
      new Employee(1, "Mike", 1),
      new Employee(2, "John", 1),
      new Employee(3, "Mary", 1),
      new Employee(4, "Joe", 2),
      new Employee(5, "Nicole", 2),
      new Employee(6, "Alice", 2),
      new Employee(7, "Bob", 3),
      new Employee(8, "Scarlett", 3));
}

private List<String> employeeNameFilter() {
    return Arrays.asList("Alice", "Mike", "Bob");
}

For our example, we'll filter the first list of Employees based on the second list with Employee names to find only the Employees with those specific names.

Now, let's see the traditional approach – looping through both lists looking for matches:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingForEachLoop() {
    List<Employee> filteredList = new ArrayList<>();
    List<Employee> originalList = buildEmployeeList();
    List<String> nameFilter = employeeNameFilter();

    for (Employee employee : originalList) {
        for (String name : nameFilter) {
            if (employee.getName().equals(name)) {
                filteredList.add(employee);
                // break;
            }
        }
    }

    assertThat(filteredList.size(), is(nameFilter.size()));
}

This is a simple syntax, but it's quite verbose, and actually quite inefficient. Simply put, it iterates through the Cartesian product of the two sets in order to get our answer.

Even adding a break to exit early will still iterate on the same order as a Cartesian product in the average case.

If we call the size of the employee list n, then nameFilter will be on the order just as big, giving us an O(n2classification.

3. Using Streams and List#contains

We'll now refactor the previous method by using lambdas to simplify syntax and improve readability. Let's also use the List#contains method as the lambda filter:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingLambda() {
    List<Employee> filteredList;
    List<Employee> originalList = buildEmployeeList();
    List<String> nameFilter = employeeNameFilter();

    filteredList = originalList.stream()
      .filter(employee -> nameFilter.contains(employee.getName()))
      .collect(Collectors.toList());

    assertThat(filteredList.size(), is(nameFilter.size()));
}

By using the Stream API, readability has been greatly improved, but our code remains as inefficient as our previous method because it's still iterating through the Cartesian product internally. Thus, we have the same O(n2classification.

4. Using Streams with HashSet

To improve performance, we must use the HashSet#contains method. This method differs from List#contains because it performs a hash code lookup, giving us a constant-time number of operations:

@Test
public void givenEmployeeList_andNameFilterList_thenObtainFilteredEmployeeList_usingLambdaAndHashSet() {
    List<Employee> filteredList;
    List<Employee> originalList = buildEmployeeList();
    Set<String> nameFilterSet = employeeNameFilter().stream().collect(Collectors.toSet());

    filteredList = originalList.stream()
      .filter(employee -> nameFilterSet.contains(employee.getName()))
      .collect(Collectors.toList());

    assertThat(filteredList.size(), is(nameFilterSet.size()));
}

By using HashSet, our code efficiency has vastly improved while not affecting readability. Since HashSet#contains runs in constant time, we've improved our classification to O(n).

5. Conclusion

In this quick tutorial, we learned how to filter a Collection by a List of values and the drawbacks of using what may seem like the most straightforward method.

We must always consider efficiency because our code might end up running in huge data sets, and performance issues could have catastrophic consequences in such environments.

All code presented in this article is available over on GitHub.

Java bottom

I just announced the new Learn Spring course, focused on the fundamentals of Spring 5 and Spring Boot 2:

>> CHECK OUT THE COURSE
newest oldest most voted
Notify of
Jose
Guest
Jose

Interesting article, but a bit misleading. True is that use streams is pretty cool and readable but say you are gonna have better performance, with difference, compare with the for loop, it’s not totally true.
If you change the inner for loop with a collection contains you can get similar times.
Size of the data list will affect, for small sets, for loop give better performance. we shall move to data sets of 80000 to be able to see better performance with Streams.
I will specify that in your article.

Eric Martin
Member
Eric Martin

Hello Jose,
Thank you for your feedback. However, the article doesn’t mention that streams are faster than for loops. But you have a point with .contains() inside the for loop, we missed that. We’ll update the article.
Cheers.

Comments are closed on this article!