2. 概述

在日常开发中,我们经常需要根据一个 List 来过滤另一个 Collection。虽然实现方法多种多样,但如果选择不当,很容易写出性能低下的代码。

这篇文章会带你对比几种常见的过滤方式,分析它们的优劣,让你在实际开发中能做出更合适的选择。✅

3. 使用 for-each 循环

先来看最经典的做法:嵌套 for-each 循环。

以下是我们示例中用到的类:

public class Employee {

    private Integer employeeNumber;
    private String name;
    private Integer departmentId;
    // 标准构造函数、getter 和 setter 省略
}

以及两个辅助方法:

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

我们的目标是:从员工列表中筛选出名字在 employeeNameFilter 中的员工。

下面是传统的双重循环写法:

@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()));
}

这种方式虽然逻辑清晰,但效率低下。本质上是在遍历两个集合的笛卡尔积 ❌。即使加上 break,也改变不了最坏情况下的时间复杂度。

假设员工列表大小为 n,那么 nameFilter 的大小也接近 n,整体时间复杂度为 **O(n²)**。

4. 使用 Stream 和 List#contains

接下来我们用 Java 8 的 Stream API 改写一下,提升代码可读性:

@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()));
}

虽然代码更简洁、可读性更强 ✅,但性能上并没有提升,因为 List#contains 依然是线性查找,整体复杂度还是 O(n²) ❌。

5. 使用 Stream 和 HashSet

要提升性能,关键在于使用 HashSet#contains,它基于哈希查找,时间复杂度为常数级:

@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()));
}

通过将过滤条件转换为 HashSet,我们不仅保持了代码的简洁性,还将时间复杂度优化到了 O(n) ✅。这才是我们真正想要的高性能方案。

6. 总结

在这篇文章中,我们对比了几种通过 List 过滤 Collection 的方式:

方法 时间复杂度 可读性 推荐度
嵌套 for-each O(n²) 一般
Stream + List.contains O(n²) ⚠️
Stream + HashSet.contains O(n)

在处理大量数据时,性能问题可能会带来严重后果,因此选择合适的数据结构至关重要。记住:不要被“看起来简单”的写法迷惑,要从算法复杂度角度出发思考问题。💡


原始标题:Filtering a Java Collection by a List | Baeldung