 到 O(n+m) 的查询提速案例)
1. 前言刚入行的时候我在一家还不错的小公司从事股票交易软件的开发。当时要做一个成交额数据看板的功能需要从成交额表中查询出指定时间段的数据按照三个维度处理数据。编写程序的时候用了三层循环在测试环境完美测试通过了。但是上生产环境的时候出现了接口请求五分钟都无反应的问题。经过排查发现是正式环境数据仓库中的这个表的数据量是亿级别的数据处理太久。我将其中一层循环改成map后5秒钟就查询出结果了。所以减少循环的层次可以提高代码执行的效率数据量越大越能体现这个优化。2. 问题场景假设现在有一个需求找出两个列表中userId相同的所有用户姓名。listA5 万条用户记录listB8 万条用户记录优化前的朴素实现使用双层嵌套循环遍历listA的每个元素再在内层遍历整个listB做匹配。当listA有 5 万条、listB有 8 万条时内层比较总计执行约40 亿次这就是接口变慢的根源。3. 优化前双层嵌套循环// 优化前双层嵌套循环 O(n * m)staticListStringfindSameUsersByNestedLoop(ListUserlistA,ListUserlistB){ListStringresultnewArrayList();for(Usera:listA){for(Userb:listB){if(a.userIdb.userId){result.add(a.name-b.name);}}}returnresult;}上述代码虽然写法直观但存在明显的性能隐患外层循环执行n次内层循环执行m次总的比较次数为n × m时间复杂度为O(n × m)即平方级别。当n和m都达到万级以上时执行时间会成倍增长。4. 优化后HashMap 替代嵌套循环优化的核心思路是「用空间换时间」先把其中一个列表的userId与姓名存入HashMap之后遍历另一个列表时用get方法以 O(1) 的时间完成匹配从而把两层循环削减成两个独立的单层循环。// 优化后HashMap 映射 O(n m)staticListStringfindSameUsersByMap(ListUserlistA,ListUserlistB){// 以 userId 为键建立 listB 的索引MapInteger,UsermapBnewHashMap();for(Userb:listB){mapB.put(b.userId,b);}ListStringresultnewArrayList();for(Usera:listA){UsermatchedmapB.get(a.userId);if(matched!null){result.add(a.name-matched.name);}}returnresult;}优化后的逻辑拆成两步遍历listA构建userId - name的哈希映射耗时 O(n)遍历listB通过map.get直接查找耗时 O(m)。整个流程的时间复杂度降为O(n m)也就是线性级别。5. 完整可运行示例与时间对比下面是一段完整可运行的 Java 代码在main方法中生成 5 万条和 8 万条随机数据分别运行优化前后的方法并打印耗时importjava.util.*;publicclassNestedLoopOptimize{staticclassUser{intuserId;Stringname;User(intuserId,Stringname){this.userIduserId;this.namename;}}// 优化前双层嵌套循环 O(n * m)staticListStringfindSameUsersByNestedLoop(ListUserlistA,ListUserlistB){ListStringresultnewArrayList();for(Usera:listA){for(Userb:listB){if(a.userIdb.userId){result.add(a.name-b.name);}}}returnresult;}// 优化后HashMap 映射 O(n m)staticListStringfindSameUsersByMap(ListUserlistA,ListUserlistB){// 以 userId 为键建立 listB 的索引MapInteger,UsermapBnewHashMap();for(Userb:listB){mapB.put(b.userId,b);}ListStringresultnewArrayList();for(Usera:listA){UsermatchedmapB.get(a.userId);if(matched!null){result.add(a.name-matched.name);}}returnresult;}publicstaticvoidmain(String[]args){intn50000;// listA 数据量intm80000;// listB 数据量ListUserlistAnewArrayList(n);ListUserlistBnewArrayList(m);for(inti0;in;i){// id:0-49999listA.add(newUser(i,Ai));}for(inti0;im;i){// id:20000-999999listB.add(newUser(i20000,B(i20000)));}longstartSystem.currentTimeMillis();ListStringr1findSameUsersByNestedLoop(listA,listB);longcost1System.currentTimeMillis()-start;startSystem.currentTimeMillis();ListStringr2findSameUsersByMap(listA,listB);longcost2System.currentTimeMillis()-start;System.out.println(双层循环结果数r1.size()耗时cost1 ms);System.out.println(HashMap 结果数r2.size()耗时cost2 ms);}}5.1 典型运行结果在我本机运行上述代码得到如下典型输出双层循环结果数30000耗时13703 ms HashMap 结果数30000耗时32 ms两个方案返回的结果数量完全一致说明优化没有改变业务语义但耗时从13703 ms下降到32 ms提升超过 400 倍。5.2 运行时间说明运行时间会受到机器 CPU、JDK 版本、JVM 参数以及数据分布等因素影响但无论环境如何二者的量级差异都非常稳定双层嵌套循环内层比较约50000 × 80000 4 × 10^940 亿次耗时通常在秒级HashMap 方案两次线性遍历加哈希查找总计约 13 万次操作耗时通常在几十毫秒。只要数据规模达到万级以上这个优化收益就会非常明显。6. 时间复杂度对比方案核心操作时间复杂度空间复杂度适用规模双层嵌套循环双重 for 匹配O(n × m)O(1)数据量极小HashMap 映射构建哈希表 线性查找O(n m)O(n)万级、十万级甚至更大补充说明几点空间换时间HashMap 方案额外占用了 O(n) 的哈希表空间但对于现代服务器内存来说几万条映射的内存开销几乎可以忽略。哈希冲突理想情况下get是 O(1)极端冲突下会退化为 O(k)但Integer作为 key 时哈希分布均匀实际性能稳定。更通用的思路凡是「根据某个键关联两个集合」或「判断某个值是否出现过」都可以优先考虑HashMap/HashSet。7. 其他减少循环次数的常见手段除了用HashMap替代嵌套循环日常开发中还可以结合场景使用以下技巧进一步优化提前终止在查找型循环中一旦命中目标立即break或return避免无谓的后续遍历。双指针当两个序列已排序时用双指针同步扫描复杂度可降到 O(n)。缓存中间结果把重复计算的表达式或查询结果缓存到局部变量 / Map避免在循环体内反复计算。位图 / 布隆过滤器用于大规模「是否存在」判断大幅降低空间占用。这些方法的核心目标一致减少不必要的循环次数把平方级复杂度降到线性甚至常数级。8. 总结本文通过一个「查找两个列表中相同 userId 用户」的实例展示了循环嵌套优化的完整过程优化前使用双层for循环时间复杂度为 O(n × m)5 万 × 8 万的数据量下耗时约 8 秒优化后使用HashMap先建映射、再做线性查找时间复杂度降为 O(n m)同样数据量下耗时仅约 32 毫秒两个方案输出结果一致验证了「空间换时间」策略在保证正确性的前提下能带来超过 400 倍的性能提升。在实际业务中遇到两个集合的匹配、关联或去重逻辑时建议优先考虑用HashMap或HashSet替代嵌套循环这是最直接、最有效的查询提速手段之一。 循环嵌套优化实战：从 O(n×m) 到 O(n+m) 的查询提速案例
1. 前言刚入行的时候我在一家还不错的小公司从事股票交易软件的开发。当时要做一个成交额数据看板的功能需要从成交额表中查询出指定时间段的数据按照三个维度处理数据。编写程序的时候用了三层循环在测试环境完美测试通过了。但是上生产环境的时候出现了接口请求五分钟都无反应的问题。经过排查发现是正式环境数据仓库中的这个表的数据量是亿级别的数据处理太久。我将其中一层循环改成map后5秒钟就查询出结果了。所以减少循环的层次可以提高代码执行的效率数据量越大越能体现这个优化。2. 问题场景假设现在有一个需求找出两个列表中userId相同的所有用户姓名。listA5 万条用户记录listB8 万条用户记录优化前的朴素实现使用双层嵌套循环遍历listA的每个元素再在内层遍历整个listB做匹配。当listA有 5 万条、listB有 8 万条时内层比较总计执行约40 亿次这就是接口变慢的根源。3. 优化前双层嵌套循环// 优化前双层嵌套循环 O(n * m)staticListStringfindSameUsersByNestedLoop(ListUserlistA,ListUserlistB){ListStringresultnewArrayList();for(Usera:listA){for(Userb:listB){if(a.userIdb.userId){result.add(a.name-b.name);}}}returnresult;}上述代码虽然写法直观但存在明显的性能隐患外层循环执行n次内层循环执行m次总的比较次数为n × m时间复杂度为O(n × m)即平方级别。当n和m都达到万级以上时执行时间会成倍增长。4. 优化后HashMap 替代嵌套循环优化的核心思路是「用空间换时间」先把其中一个列表的userId与姓名存入HashMap之后遍历另一个列表时用get方法以 O(1) 的时间完成匹配从而把两层循环削减成两个独立的单层循环。// 优化后HashMap 映射 O(n m)staticListStringfindSameUsersByMap(ListUserlistA,ListUserlistB){// 以 userId 为键建立 listB 的索引MapInteger,UsermapBnewHashMap();for(Userb:listB){mapB.put(b.userId,b);}ListStringresultnewArrayList();for(Usera:listA){UsermatchedmapB.get(a.userId);if(matched!null){result.add(a.name-matched.name);}}returnresult;}优化后的逻辑拆成两步遍历listA构建userId - name的哈希映射耗时 O(n)遍历listB通过map.get直接查找耗时 O(m)。整个流程的时间复杂度降为O(n m)也就是线性级别。5. 完整可运行示例与时间对比下面是一段完整可运行的 Java 代码在main方法中生成 5 万条和 8 万条随机数据分别运行优化前后的方法并打印耗时importjava.util.*;publicclassNestedLoopOptimize{staticclassUser{intuserId;Stringname;User(intuserId,Stringname){this.userIduserId;this.namename;}}// 优化前双层嵌套循环 O(n * m)staticListStringfindSameUsersByNestedLoop(ListUserlistA,ListUserlistB){ListStringresultnewArrayList();for(Usera:listA){for(Userb:listB){if(a.userIdb.userId){result.add(a.name-b.name);}}}returnresult;}// 优化后HashMap 映射 O(n m)staticListStringfindSameUsersByMap(ListUserlistA,ListUserlistB){// 以 userId 为键建立 listB 的索引MapInteger,UsermapBnewHashMap();for(Userb:listB){mapB.put(b.userId,b);}ListStringresultnewArrayList();for(Usera:listA){UsermatchedmapB.get(a.userId);if(matched!null){result.add(a.name-matched.name);}}returnresult;}publicstaticvoidmain(String[]args){intn50000;// listA 数据量intm80000;// listB 数据量ListUserlistAnewArrayList(n);ListUserlistBnewArrayList(m);for(inti0;in;i){// id:0-49999listA.add(newUser(i,Ai));}for(inti0;im;i){// id:20000-999999listB.add(newUser(i20000,B(i20000)));}longstartSystem.currentTimeMillis();ListStringr1findSameUsersByNestedLoop(listA,listB);longcost1System.currentTimeMillis()-start;startSystem.currentTimeMillis();ListStringr2findSameUsersByMap(listA,listB);longcost2System.currentTimeMillis()-start;System.out.println(双层循环结果数r1.size()耗时cost1 ms);System.out.println(HashMap 结果数r2.size()耗时cost2 ms);}}5.1 典型运行结果在我本机运行上述代码得到如下典型输出双层循环结果数30000耗时13703 ms HashMap 结果数30000耗时32 ms两个方案返回的结果数量完全一致说明优化没有改变业务语义但耗时从13703 ms下降到32 ms提升超过 400 倍。5.2 运行时间说明运行时间会受到机器 CPU、JDK 版本、JVM 参数以及数据分布等因素影响但无论环境如何二者的量级差异都非常稳定双层嵌套循环内层比较约50000 × 80000 4 × 10^940 亿次耗时通常在秒级HashMap 方案两次线性遍历加哈希查找总计约 13 万次操作耗时通常在几十毫秒。只要数据规模达到万级以上这个优化收益就会非常明显。6. 时间复杂度对比方案核心操作时间复杂度空间复杂度适用规模双层嵌套循环双重 for 匹配O(n × m)O(1)数据量极小HashMap 映射构建哈希表 线性查找O(n m)O(n)万级、十万级甚至更大补充说明几点空间换时间HashMap 方案额外占用了 O(n) 的哈希表空间但对于现代服务器内存来说几万条映射的内存开销几乎可以忽略。哈希冲突理想情况下get是 O(1)极端冲突下会退化为 O(k)但Integer作为 key 时哈希分布均匀实际性能稳定。更通用的思路凡是「根据某个键关联两个集合」或「判断某个值是否出现过」都可以优先考虑HashMap/HashSet。7. 其他减少循环次数的常见手段除了用HashMap替代嵌套循环日常开发中还可以结合场景使用以下技巧进一步优化提前终止在查找型循环中一旦命中目标立即break或return避免无谓的后续遍历。双指针当两个序列已排序时用双指针同步扫描复杂度可降到 O(n)。缓存中间结果把重复计算的表达式或查询结果缓存到局部变量 / Map避免在循环体内反复计算。位图 / 布隆过滤器用于大规模「是否存在」判断大幅降低空间占用。这些方法的核心目标一致减少不必要的循环次数把平方级复杂度降到线性甚至常数级。8. 总结本文通过一个「查找两个列表中相同 userId 用户」的实例展示了循环嵌套优化的完整过程优化前使用双层for循环时间复杂度为 O(n × m)5 万 × 8 万的数据量下耗时约 8 秒优化后使用HashMap先建映射、再做线性查找时间复杂度降为 O(n m)同样数据量下耗时仅约 32 毫秒两个方案输出结果一致验证了「空间换时间」策略在保证正确性的前提下能带来超过 400 倍的性能提升。在实际业务中遇到两个集合的匹配、关联或去重逻辑时建议优先考虑用HashMap或HashSet替代嵌套循环这是最直接、最有效的查询提速手段之一。