如何将Java嵌套循环转换为HashMap以降低时间复杂度

原代码通过嵌套循环匹配Object1和Object2的name属性，时间复杂度为O(N*M)（N是listObject1的长度，M是listObject2的长度），当数据量较大时性能会显著下降。我们可以通过HashMap分组+Stream将时间复杂度优化到O(N+M)，具体实现如下：

核心思路 #

1. 先将所有Object2按name属性分组存入HashMap，这样根据name查找对应Object2列表的时间复杂度为O(1)
2. 遍历Object1列表，直接从HashMap中获取匹配的Object2列表并赋值

优化后的代码 #

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public void fillNestedObject() {
    List<Object1> listObject1 = fetchObjects1FromApi();
    List<Object2> listObject2 = fetchObjectsFromApi2();
    
    // 用Stream将Object2按name分组，生成name到对应Object2列表的映射
    Map<String, List<Object2>> object2ByName = listObject2.stream()
        .collect(Collectors.groupingBy(Object2::getName));
    
    // 遍历Object1列表，快速匹配对应Object2列表
    listObject1.forEach(object1 -> {
        // 用getOrDefault避免空指针，没有匹配到则返回空列表
        List<Object2> matchedObject2 = object2ByName.getOrDefault(object1.getName(), Collections.emptyList());
        object1.setListObject2(new ArrayList<>(matchedObject2));
    });
}

细节说明 #

• Collectors.groupingBy(Object2::getName)会自动将相同name的Object2归为同一列表，作为HashMap的value
• 使用getOrDefault可以避免当Object1的name在Object2中不存在时出现NullPointerException，返回空列表替代
• 如果需要保证listObject2是可修改的列表（比如后续要添加元素），可以用new ArrayList<>(matchedObject2)包装，因为groupingBy返回的列表可能是不可变的（取决于JDK版本和实现）

时间复杂度对比 #

• 原代码：嵌套循环，时间复杂度O(N*M)
• 优化后：分组操作O(M) + 遍历赋值O(N)，总时间复杂度O(N+M)，数据量越大，性能提升越明显

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