公司来了个新同事，把代码耗时从 26856ms 优化到了 748ms，一顿操作猛如虎！

在两张表中查找相同 ID 的数据时，许多开发者会使用两层 for 循环嵌套。 这种写法效率较低，本文将介绍一种提高查找速度的优化方法。

场景

在 for 循环内嵌套 for 循环，进行数据匹配和处理。时间复杂度为 O(n*m)，在数据量较大时性能会急剧下降。

示例

假设有两份 List 数据： userList 和 userMemoList 。需要遍历 userList ，根据每个用户的 userId ，从 userMemoList 中查找并取出对应 userId 的 content 值进行后续处理。

import lombok.Data;
import java.util.*;
import java.util.stream.Collectors;
import org.springframework.util.StringUtils;

@Data
class User {
    private Long userId;
    private String name;
}

@Data
class UserMemo {
    private Long userId;
    private String content;
}

public class NestedLoopOptimization {

    public static List getUserTestList() {
        List users = new ArrayList<>();
        for (int i = 1; i <= 50000; i++) {
            User user = new User();
            user.setName(UUID.randomUUID().toString());
            user.setUserId((long) i);
            users.add(user);
        }
        return users;
    }

    public static List getUserMemoTestList() {
        List userMemos = new ArrayList<>();
        for (int i = 30000; i >= 1; i--) {
            UserMemo userMemo = new UserMemo();
            userMemo.setContent(UUID.randomUUID().toString());
            userMemo.setUserId((long) i);
            userMemos.add(userMemo);
        }
        return userMemos;
    }

// ... 后续代码
}

模拟数据：5 万条 user 数据，3 万条 userMemo 数据。

未优化的代码

最直接的实现方式，通过两层 for 循环进行匹配：

    public static void nestedLoop(List userTestList, List userMemoTestList) {
        for (User user : userTestList) {
            Long userId = user.getUserId();
            for (UserMemo userMemo : userMemoTestList) {
                if (userId.equals(userMemo.getUserId())) {
                    String content = userMemo.getContent();
                    // System.out.println("模拟数据content 业务处理......" + content); // 避免打印影响测试结果
                }
            }
        }
    }

耗时：约数万毫秒 (5 万 * 3 万次迭代)。

ps：其实数据量小的话，其实没多大性能差别，不过我们还是需要知道一些技巧点。

break 优化

当每个 userId 在 userMemoList 中只有一条数据时，找到匹配项后直接 break 跳出内循环：

    public static void breakOptimizedLoop(List userTestList, List userMemoTestList) {
        for (User user : userTestList) {
            Long userId = user.getUserId();
            for (UserMemo userMemo : userMemoTestList) {
                if (userId.equals(userMemo.getUserId())) {
                    String content = userMemo.getContent();
                    // System.out.println("模拟数据content 业务处理......" + content); // 避免打印影响测试结果
                    break; // 找到匹配项后跳出内循环
                }
            }
        }
    }

耗时：仍然需要遍历较多次，但比嵌套循环略有改善。

使用 Map 优化

    public static void mapOptimizedLoop(List userTestList, List userMemoTestList) {
        Map contentMap = userMemoTestList.stream().collect(Collectors.toMap(UserMemo::getUserId, UserMemo::getContent));

        for (User user : userTestList) {
            Long userId = user.getUserId();
            String content = contentMap.get(userId);

            if (StringUtils.hasLength(content)) {
               // System.out.println("模拟数据content 业务处理......" + content); // 避免打印影响测试结果
            }
        }
    }

耗时：显著减少，通常在数百毫秒级别。

原理

两层 for 循环嵌套的时间复杂度为 O(n*m)，其中 n 和 m 分别为两个列表的长度。使用 Map 后， get 操作的时间复杂度接近 O(1)，整体时间复杂度降为 O(n+m)，避免了内循环的重复遍历。

HashMap 的 get 方法内部使用了 getNode 方法来查找键值对。 getNode 方法利用哈希表结构，快速定位到目标键值对。虽然在极端情况下（所有键的哈希值都相同）， getNode 的时间复杂度会退化为 O(n)，但在实际应用中，哈希冲突的概率很低， HashMap 的 get 操作效率通常很高。因此无需过于担心 O(n) 的最坏情况.

//  HashMap.getNode() 方法的部分关键代码 (JDK8)
final Node getNode(int hash, Object key) {
    // ... (省略部分代码)
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first; //  找到节点，直接返回
    // ... (省略处理哈希冲突的代码)
}

通过以上优化，可以显著提高代码的执行效率。尤其是在处理大量数据时，使用 Map 优化能够带来巨大的性能提升。避免了不必要的计算，从而提升了代码的性能。

总结