本文旨在提供一种使用 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 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);
}
}
} 代码解释
创建 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 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 版本）
转换为 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 提供了另一种简洁的实现方式，但在选择时需要考虑实际场景和性能需求。在实际应用中，应根据数据量和性能要求选择最合适的优化方法。
