公司来了个新同事，把代码耗时从 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<User> getUserTestList() { List<User> 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<UserMemo> getUserMemoTestList() { List<UserMemo> 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<User> userTestList, List<UserMemo> 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<User> userTestList, List<UserMemo> 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<User> userTestList, List<UserMemo> userMemoTestList) { Map<Long, String> 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<K,V> getNode(int hash, Object key) { // ... (省略部分代码) if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 找到节点，直接返回 // ... (省略处理哈希冲突的代码) }

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

总结