Java中高效合并两个Map并忽略键去除重复值的方法

核心思路 #

要避免嵌套遍历的O(n²)复杂度，我们可以利用HashSet的O(1)查找特性，先将两个Map的value集合存入HashSet，再通过一次遍历筛选符合条件的键值对，整体时间复杂度优化为O(n)。

实现代码 #

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class MapValueMismatch {
    public static void main(String[] args) {
        Map<String, String> carColors = new HashMap<>();
        carColors.put("FirstCar", "Blue");
        carColors.put("SecondCar", "Yellow");
        carColors.put("ThirdCar", "Green");

        Map<String, String> colorsOfCars = new HashMap<>();
        colorsOfCars.put("FirstCar", "Yellow");
        colorsOfCars.put("SecondCar", "Blue");
        colorsOfCars.put("ThirdCar", "Orange");

        // 复制原Map避免修改原数据或并发问题
        Map<String, String> dup1 = new HashMap<>(carColors);
        Map<String, String> dup2 = new HashMap<>(colorsOfCars);

        // 将两个Map的value存入HashSet，用于快速查找
        Set<String> carColorValues = new HashSet<>(dup1.values());
        Set<String> colorOfCarValues = new HashSet<>(dup2.values());

        Map<String, String> result = new HashMap<>();

        // 遍历共同键（假设两个Map键集合一致，若不一致可先取交集）
        for (String key : dup1.keySet()) {
            if (!dup2.containsKey(key)) {
                // 若键仅存在于dup1，直接加入结果
                result.put(key, dup1.get(key));
                continue;
            }
            String val1 = dup1.get(key);
            String val2 = dup2.get(key);
            // 判断当前键的两个值是否都不在对方的value集合中
            if (!colorOfCarValues.contains(val1) || !carColorValues.contains(val2)) {
                // 这里可以选择存入dup1的值、dup2的值，或者两者都存，示例中存入dup1的
                result.put(key, val1);
                // 如果需要同时保留两个值，可以用Map<String, List<String>>存储
                // result.put(key, Arrays.asList(val1, val2));
            }
        }

        // 输出结果：{ThirdCar=Green}
        System.out.println(result);
    }
}

关键细节 #

• HashSet的作用：将value集合转为HashSet后，判断某个值是否存在的操作从O(n)变为O(1)，大幅提升查找效率。
• 键集合的处理：如果两个Map的键集合不一致，可先通过dup1.keySet().retainAll(dup2.keySet())获取共同键，再遍历；若需要保留仅存在于单个Map的键，直接加入结果即可。
• 结果存储方式：示例中仅存入第一个Map的value，若需要同时保留两个Map中该键的value，可改用Map<String, List<String>>存储。

复杂度对比 #

• 原嵌套遍历方式：时间复杂度O(n²)，大数据集下性能急剧下降。
• 优化后的方式：时间复杂度O(n)，空间复杂度O(n)（用于存储HashSet），在大数据集下性能优势明显。

内容的提问来源于stack exchange，提问作者Abdul Rahim Khan