如何高效查找两个含Map的ArrayList中的差异元素？

当然有更高效的解法啦！你现在的嵌套循环方案虽然能正确得到结果，但时间复杂度是O(n*m)——当两个列表的元素数量较多时，性能会明显下降。我们可以借助哈希集合的快速查找特性，把时间复杂度优化到O(n+m)，大幅提升效率。

核心思路 #

我们的目标是找出：

• lOld：仅存在于a2中的元素
• lNew：仅存在于a1中的元素

判断元素是否“重复”的依据是Map中的val值（从你的示例逻辑可知）。哈希集合的contains操作时间复杂度是O(1)，所以我们可以先把两个列表中所有的val值提取到集合中，再通过一次遍历就能筛选出差异元素。

优化后的代码（Java 8+ Stream版） #

import java.util.*;
import java.util.stream.Collectors;

public class ListDiffExample {
    public static void main(String[] args) {
        // 示例数据
        List<Map<String, String>> a1 = Arrays.asList(
                Map.of("val", "1", "id", "19"),
                Map.of("val", "2", "id", "22"),
                Map.of("val", "3", "id", "2"),
                Map.of("val", "4", "id", "49")
        );

        List<Map<String, String>> a2 = Arrays.asList(
                Map.of("val", "1", "id", "12"),
                Map.of("val", "2", "id", "22"),
                Map.of("val", "3", "id", "32"),
                Map.of("val", "5", "id", "52")
        );

        // 提取a1中所有val值到哈希集合
        Set<String> a1ValSet = a1.stream()
                .map(map -> map.get("val"))
                .collect(Collectors.toSet());

        // 提取a2中所有val值到哈希集合
        Set<String> a2ValSet = a2.stream()
                .map(map -> map.get("val"))
                .collect(Collectors.toSet());

        // 筛选仅在a2中存在的元素（lOld）
        List<Map<String, String>> lOld = a2.stream()
                .filter(map -> !a1ValSet.contains(map.get("val")))
                .collect(Collectors.toList());

        // 筛选仅在a1中存在的元素（lNew）
        List<Map<String, String>> lNew = a1.stream()
                .filter(map -> !a2ValSet.contains(map.get("val")))
                .collect(Collectors.toList());

        // 输出结果
        System.out.println("lOld = " + lOld);
        System.out.println("lNew = " + lNew);
    }
}

兼容低版本Java的写法 #

如果你使用的是Java 8之前的版本，可以用普通循环实现相同逻辑：

import java.util.*;

public class ListDiffExample {
    public static void main(String[] args) {
        // 示例数据初始化同前...

        Set<String> a1ValSet = new HashSet<>();
        for (Map<String, String> map : a1) {
            a1ValSet.add(map.get("val"));
        }

        Set<String> a2ValSet = new HashSet<>();
        for (Map<String, String> map : a2) {
            a2ValSet.add(map.get("val"));
        }

        List<Map<String, String>> lOld = new ArrayList<>();
        for (Map<String, String> map : a2) {
            if (!a1ValSet.contains(map.get("val"))) {
                lOld.add(map);
            }
        }

        List<Map<String, String>> lNew = new ArrayList<>();
        for (Map<String, String> map : a1) {
            if (!a2ValSet.contains(map.get("val"))) {
                lNew.add(map);
            }
        }

        // 输出结果同前...
    }
}

扩展：多键判断元素是否相同 #

如果你的需求是多个键的组合相同才算同一元素（比如同时比较val和id），只需要把这些键组合成一个唯一标识存入集合即可：

// 组合val和id作为唯一键
Set<String> a1KeySet = a1.stream()
        .map(map -> map.get("val") + "|" + map.get("id"))
        .collect(Collectors.toSet());

// 后续筛选逻辑和之前一致，只是判断的是组合键

结果验证 #

用你的示例数据测试，优化后的代码会输出和预期完全一致的结果：

lOld = [{"val":"5","id":"52"}]
lNew = [{"val":"4","id":"49"}]

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