Java对比两个集合筛选增删元素的代码性能优化咨询

优化建议 #

性能瓶颈分析 #

你当前实现的性能短板在于ArrayList的contains()方法：该方法需要逐个遍历列表元素匹配，时间复杂度为O(n)。假设当前列表长度为m，新列表长度为n，整体时间复杂度为O(m*n)，当列表元素量级上千的时候性能下降会非常明显。

核心优化方案 #

将存在性判断的数据源从ArrayList替换为HashSet，HashSet的contains()方法基于哈希表实现，时间复杂度稳定为O(1)，优化后整体时间复杂度可以降到O(m + n)，性能提升非常显著。

优化后的test方法代码示例：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public static void test(List<String> currentCodes, List<String> newCodes) {
    System.out.println("current" + currentCodes + " ; new" + newCodes);

    // 先转成HashSet用于O(1)复杂度的存在性判断
    Set<String> newCodeSet = new HashSet<>(newCodes);
    Set<String> currentCodeSet = new HashSet<>(currentCodes);

    List<String> codesToRemove = new ArrayList<>();
    for (String currentCode : currentCodes) {
        if (!newCodeSet.contains(currentCode)) {
            // 原有业务逻辑保留
            codesToRemove.add(currentCode);
        }
    }

    List<String> codesToAdd = new ArrayList<>();
    for (String newCode : newCodes) {
        if (!currentCodeSet.contains(newCode)) {
            // 原有业务逻辑保留
            codesToAdd.add(newCode);
        }
    }

    System.out.println("removeResult" + codesToRemove);
    System.out.println("addResult" + codesToAdd);
    System.out.println("......................................");
}

可选简化写法（Java 8+） #

如果你的项目支持Java 8及以上版本，可以用Stream API简化遍历逻辑，性能和上面的实现一致：

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public static void test(List<String> currentCodes, List<String> newCodes) {
    System.out.println("current" + currentCodes + " ; new" + newCodes);
    
    Set<String> newCodeSet = new HashSet<>(newCodes);
    Set<String> currentCodeSet = new HashSet<>(currentCodes);
    
    List<String> codesToRemove = currentCodes.stream()
            .filter(code -> !newCodeSet.contains(code))
            .collect(Collectors.toList());
    List<String> codesToAdd = newCodes.stream()
            .filter(code -> !currentCodeSet.contains(code))
            .collect(Collectors.toList());
    
    System.out.println("removeResult" + codesToRemove);
    System.out.println("addResult" + codesToAdd);
    System.out.println("......................................");
}

补充说明 #

如果你的业务场景中允许code重复，需要保留重复元素的增删统计，那么可以用HashMap统计元素出现次数来替代HashSet，逻辑同理，性能也能维持在O(m+n)的水平。

内容的提问来源于stack exchange，提问作者Kapparino