核心内容摘要
中文字幕第一：穿越语言的藩篱，连接世界的精彩
在两张表中查找相同 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 ListUser getUserTestList() { ListUser 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 ListUserMemo getUserMemoTestList() { ListUserMemo 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(ListUser userTestList, ListUserMemo 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(ListUser userTestList, ListUserMemo 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(ListUser userTestList, ListUserMemo userMemoTestList) { MapLong, 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(
整体时间复杂度降为 O(nm)避免了内循环的重复遍历。
HashMap的get方法内部使用了getNode方法来查找键值对。
getNode方法利用哈希表结构快速定位到目标键值对。
虽然在极端情况下所有键的哈希值都相同getNode的时间复杂度会退化为 O(n)但在实际应用中哈希冲突的概率很低HashMap的get操作效率通常很高。
因此无需过于担心O(n)的最坏情况.// HashMap.getNode() 方法的部分关键代码 (JDK
final NodeK,V getNode(int hash, Object key) { // ... (省略部分代码) if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 找到节点直接返回 // ... (省略处理哈希冲突的代码) }通过以上优化可以显著提高代码的执行效率。
尤其是在处理大量数据时使用Map优化能够带来巨大的性能提升。
避免了不必要的计算从而提升了代码的性能。