本文旨在提供一种使用 HashMap 优化 Java 中嵌套循环的有效方法，特别是当循环涉及对象数组并进行相等性检查时。通过将内部循环转换为 HashMap 查询，可以显著降低时间复杂度，提高代码性能。本文将提供详细的步骤和示例代码，帮助读者理解和应用这种优化技巧。
在处理包含嵌套循环的 Java 代码时，特别是当需要对两个对象列表进行比较并根据特定条件进行匹配时，性能往往成为一个关键问题。 传统的嵌套循环方法的时间复杂度为 O(n*m)，其中 n 和 m 分别是两个列表的长度。当列表很大时，这种方法可能会变得非常耗时。本文将介绍如何使用 HashMap 来优化这种类型的代码，将时间复杂度降低到接近 O(n+m)。
问题描述
假设我们有两个 Java 对象，Object1 和 Object2。Object1 包含字符串属性和一个 Object2 列表。我们的目标是遍历 Object1 的列表，并为每个 Object1 对象找到所有名称属性匹配的 Object2 对象，然后将这些 Object2 对象添加到 Object1 的列表中。
立即学习“Java免费学习笔记（深入）”；
public class Object1 { String name; String xyz; List<Object2> listObject2; public String getName() { return name; } public void setListObject2(List<Object2> listObject2) { this.listObject2 = listObject2; } } public class Object2 { String name; String abc; String def; public String getName() { return name; } }
传统的实现方式是使用嵌套循环：
public void fillNestedObject() { List<Object1> listObject1 = new ArrayList<>(); // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表 // 实际使用时请替换为真实数据源 listObject1.add(new Object1()); listObject1.get(0).name = "test"; List<Object2> listObject2 = new ArrayList<>(); // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表 // 实际使用时请替换为真实数据源 Object2 obj2 = new Object2(); obj2.name = "test"; listObject2.add(obj2); for(Object1 object1 : listObject1){ List<Object2> 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<Object1> listObject1 = new ArrayList<>(); // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表 // 实际使用时请替换为真实数据源 Object1 obj1 = new Object1(); obj1.name = "test"; listObject1.add(obj1); List<Object2> listObject2 = new ArrayList<>(); // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表 // 实际使用时请替换为真实数据源 Object2 obj2 = new Object2(); obj2.name = "test"; listObject2.add(obj2); // 创建一个 HashMap，以 Object2 的 name 属性作为键，Object2 对象作为值 Map<String, List<Object2>> 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<Object2> tmpList = object2Map.getOrDefault(object1.getName(), new ArrayList<>()); object1.setListObject2(tmpList); } } }
代码解释
-
创建 HashMap: 我们首先创建一个 HashMap object2Map，用于存储 Object2 对象。键是 Object2 对象的 name 属性，值是具有相同 name 属性的 Object2 对象的列表。
-
填充 HashMap: 我们遍历 listObject2，并将每个 Object2 对象添加到 object2Map 中。如果 object2Map 中已经存在具有相同 name 属性的键，则将 Object2 对象添加到该键对应的值列表中。否则，创建一个新的列表并将 Object2 对象添加到该列表中，然后将该键值对添加到 object2Map 中。
-
使用 HashMap 查找匹配对象: 我们遍历 listObject1，并使用 object2Map.get(object1.getName()) 查找与 Object1 对象匹配的 Object2 对象列表。getOrDefault 方法用于处理 object1.getName() 在 object2Map 中不存在的情况，此时返回一个新的空列表。
-
设置 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<Object1> listObject1 = new ArrayList<>(); // 假设 fetchObjects1FromApi() 从 API 获取 Object1 列表 // 实际使用时请替换为真实数据源 Object1 obj1 = new Object1(); obj1.name = "test"; listObject1.add(obj1); List<Object2> listObject2 = new ArrayList<>(); // 假设 fetchObjectsFromApi2() 从 API 获取 Object2 列表 // 实际使用时请替换为真实数据源 Object2 obj2 = new Object2(); obj2.name = "test"; listObject2.add(obj2); Stream<Object1> stream1 = listObject1.stream(); Stream<Object2> stream2 = listObject2.stream(); Map<String, List<Object2>> 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 版本）
-
转换为 Stream: 首先将 listObject1 和 listObject2 转换为 Stream 对象。
-
Reduce 成 Map: 使用 stream2.reduce 将 Object2 的 Stream 对象转换为一个 Map
>，其中 key 是 Object2 的 name 属性，value 是具有相同 name 属性的 Object2 对象列表。这个操作类似于之前手动创建 HashMap 的过程，但是使用了 Stream 的聚合操作。Collections.unmodifiableMap 用于确保 Map 的不可变性。 -
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 提供了另一种简洁的实现方式，但在选择时需要考虑实际场景和性能需求。在实际应用中，应根据数据量和性能要求选择最合适的优化方法。
评论（已关闭）
评论已关闭