HashMap优化嵌套循环：Java数组转换技巧

本文旨在提供一种使用 HashMap 优化 Java 中嵌套循环的有效方法，特别是当循环涉及对象数组并进行相等性检查时。通过将内部循环转换为 HashMap 查询，可以显著降低时间复杂度，提高代码性能。本文将提供详细的步骤和示例代码，帮助读者理解和应用这种优化技巧。

在处理包含嵌套循环的 Java 代码时，特别是当需要对两个对象列表进行比较并根据特定条件进行匹配时，性能往往成为一个关键问题。 传统的嵌套循环方法的时间复杂度为 O(n*m)，其中 n 和 m 分别是两个列表的长度。当列表很大时，这种方法可能会变得非常耗时。本文将介绍如何使用 HashMap 来优化这种类型的代码，将时间复杂度降低到接近 O(n+m)。

问题描述

假设我们有两个 Java 对象，Object1 和 Object2。Object1 包含字符串属性和一个 Object2 列表。我们的目标是遍历 Object1 的列表，并为每个 Object1 对象找到所有名称属性匹配的 Object2 对象，然后将这些 Object2 对象添加到 Object1 的列表中。

public class Object1 {
    String name;
    String xyz;
    List listObject2;

    public String getName() {
        return name;
    }

    public void setListObject2(List listObject2) {
        this.listObject2 = listObject2;
    }
}

public class Object2 {
    String name;
    String abc;
    String def;

    public String getName() {
        return name;
    }
}

传统的实现方式是使用嵌套循环：

public void fillNestedObject() {

    List listObject1 = new ArrayList<>();
    // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表
    // 实际使用时请替换为真实数据源
    listObject1.add(new Object1());
    listObject1.get(0).name = "test";

    List listObject2 = new ArrayList<>();
    // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表
    // 实际使用时请替换为真实数据源
    Object2 obj2 = new Object2();
    obj2.name = "test";
    listObject2.add(obj2);


    for(Object1 object1 : listObject1){
        List tmpList = new ArrayList<>();
        for(Object2 object2 : listObject2) {
            if(object1.getName().equals(object2.getName())){
                tmpList.add(object2);
            }
        }
        object1.setListObject2(tmpList);
    }
}

使用 HashMap 优化

为了优化上述代码，我们可以使用 HashMap 来存储 Object2 对象，以其 name 属性作为键。这样，我们就可以在 O(1) 时间复杂度内查找与 Object1 对象匹配的 Object2 对象，从而避免了内部循环。

以下是使用 HashMap 优化的代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NestedLoopOptimization {

    public void fillNestedObject() {

        List listObject1 = new ArrayList<>();
        // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表
        // 实际使用时请替换为真实数据源
        Object1 obj1 = new Object1();
        obj1.name = "test";
        listObject1.add(obj1);


        List listObject2 = new ArrayList<>();
        // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表
        // 实际使用时请替换为真实数据源
        Object2 obj2 = new Object2();
        obj2.name = "test";
        listObject2.add(obj2);


        // 创建一个 HashMap，以 Object2 的 name 属性作为键，Object2 对象作为值
        Map> object2Map = new HashMap<>();
        for (Object2 object2 : listObject2) {
            if (!object2Map.containsKey(object2.getName())) {
                object2Map.put(object2.getName(), new ArrayList<>());
            }
            object2Map.get(object2.getName()).add(object2);
        }

        // 遍历 Object1 列表，并使用 HashMap 查找匹配的 Object2 对象
        for (Object1 object1 : listObject1) {
            List tmpList = object2Map.getOrDefault(object1.getName(), new ArrayList<>());
            object1.setListObject2(tmpList);
        }
    }
}

代码解释

1. 创建 HashMap: 我们首先创建一个 HashMap object2Map，用于存储 Object2 对象。键是 Object2 对象的 name 属性，值是具有相同 name 属性的 Object2 对象的列表。

2. 填充 HashMap: 我们遍历 listObject2，并将每个 Object2 对象添加到 object2Map 中。如果 object2Map 中已经存在具有相同 name 属性的键，则将 Object2 对象添加到该键对应的值列表中。否则，创建一个新的列表并将 Object2 对象添加到该列表中，然后将该键值对添加到 object2Map 中。

3. 使用 HashMap 查找匹配对象: 我们遍历 listObject1，并使用 object2Map.get(object1.getName()) 查找与 Object1 对象匹配的 Object2 对象列表。getOrDefault 方法用于处理 object1.getName() 在 object2Map 中不存在的情况，此时返回一个新的空列表。

4. 设置 Object1 的 List: 最后将找到的 Object2 列表设置到对应的 Object1 对象的 listObject2 属性中。

使用 Java 8 Stream 优化 (原文答案)

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

public class NestedLoopOptimization {

    public void fillNestedObject() {

        List listObject1 = new ArrayList<>();
        // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表
        // 实际使用时请替换为真实数据源
        Object1 obj1 = new Object1();
        obj1.name = "test";
        listObject1.add(obj1);


        List listObject2 = new ArrayList<>();
        // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表
        // 实际使用时请替换为真实数据源
        Object2 obj2 = new Object2();
        obj2.name = "test";
        listObject2.add(obj2);

        Stream stream1 = listObject1.stream();
        Stream stream2 = listObject2.stream();

        Map> reduced2 = Collections.unmodifiableMap(
                stream2.reduce(new HashMap<>(), (a, b) -> {
                            if (!a.containsKey(b.getName())) {
                                a.put(b.getName(), new ArrayList<>());
                            }
                            a.get(b.getName()).add(b);
                            return a;
                        }, (a, b) -> b));
        stream1.peek(object1 -> object1.setListObject2(reduced2.get(object1.getName())))
                .collect(Collectors.toList());

    }
}

代码解释（Stream 版本）

1. 转换为 Stream: 首先将 listObject1 和 listObject2 转换为 Stream 对象。

2. Reduce 成 Map: 使用 stream2.reduce 将 Object2 的 Stream 对象转换为一个 Map>，其中 key 是 Object2 的 name 属性，value 是具有相同 name 属性的 Object2 对象列表。这个操作类似于之前手动创建 HashMap 的过程，但是使用了 Stream 的聚合操作。Collections.unmodifiableMap 用于确保 Map 的不可变性。

3. Peek and Collect: 使用 stream1.peek 遍历 Object1 的 Stream 对象，并为每个 Object1 对象设置其 listObject2 属性。peek 方法允许我们在不改变 Stream 的情况下执行操作。reduced2.get(object1.getName()) 从 Map 中获取与 Object1 对象的 name 属性匹配的 Object2 对象列表。最后使用 collect(Collectors.toList()) 将 Stream 转换回 List。

时间复杂度分析

• 嵌套循环: O(n*m)，其中 n 是 listObject1 的长度，m 是 listObject2 的长度。
• HashMap 优化: O(n + m)，其中 n 是 listObject1 的长度，m 是 listObject2 的长度。构建 HashMap 的时间复杂度是 O(m)，遍历 listObject1 的时间复杂度是 O(n)，而 HashMap 的查找时间复杂度是 O(1)。
• Stream 优化: 时间复杂度与 HashMap 优化类似，但 Stream 的实现可能涉及额外的开销，具体性能取决于数据量和 JVM 的优化。

总结

使用 HashMap 可以显著优化嵌套循环，特别是当需要根据特定条件匹配对象列表时。 通过将内部循环转换为 HashMap 查询，可以将时间复杂度从 O(n*m) 降低到 O(n+m)。 这种优化对于处理大型数据集至关重要。同时，Java 8 Stream 提供了另一种简洁的实现方式，但在选择时需要考虑实际场景和性能需求。在实际应用中，应根据数据量和性能要求选择最合适的优化方法。