常见踩坑点：双层 for 循环千万别这样写了！
👉 欢迎加入小哈的星球 ，你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利
全栈前后端分离博客项目 2.0 版本完结啦， 演示链接：http://116.62.199.48/ ，新项目正在酝酿中。全程手摸手，后端 + 前端全栈开发，从 0 到 1 讲解每个功能点开发步骤，1v1 答疑，直到项目上线。目前已更新了239小节，累计38w+字，讲解图：1645张，还在持续爆肝中.. 后续还会上新更多项目，目标是将Java领域典型的项目都整一波，如秒杀系统, 在线商城, IM即时通讯，Spring Cloud Alibaba 等等，戳我加入学习，已有1200+小伙伴加入(早鸟价超低)
前言
本篇分析的技巧点其实是比较常见的，但是最近的几次的代码评审还是发现有不少兄弟没注意到。
所以还是想拿出来说下。
正文
是个什么场景呢？
“
就是 for循环 里面还有 for循环， 然后做一些数据匹配、处理 这种场景。
我们结合实例代码来看看。
场景示例：
比如我们现在拿到两个list 数据 ，一个是 User List 集合 ；另一个是 UserMemo List集合；
我们需要遍历 User List ，然后根据 userId 从 UserMemo List 里面取出 对应这个userId 的 content 值，做数据处理。
代码 User.java ：
import lombok.Data;
@Data
public class User {
private Long userId;
private String name;
}
代码 UserMemo.java ：
import lombok.Data;
@Data
public class UserMemo {
private Long userId;
private String content;
}
模拟 数据集合 ：
5W 条 user 数据 ， 3W条 userMemo数据
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;
}
先看平时大家不注意的时候可能会这样去写代码处理 ：
“
ps：其实数据量小的话，其实没多大性能差别，不过我们还是需要知道一些技巧点。
代码：
public static void main(String[] args) {
List<User> userTestList = getUserTestList();
List<UserMemo> userMemoTestList = getUserMemoTestList();
StopWatch stopWatch = new StopWatch();
stopWatch.start();
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);
}
}
}
stopWatch.stop();
System.out.println("最终耗时"+stopWatch.getTotalTimeMillis());
}
我们来看看 这时候的一个耗时情况 ：
相当于迭代了 5W * 3W 次
可以看到用时 是 26857毫秒
其实到这，插入个题外点，如果说每个userId 在 UserMemo List 里面 都是只有一条数据的场景。
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);
}
}
}
单从这段代码有没有问题 ，有没有优化点。
显然是有的， 因为当我们从内循环UserMemo List里面找到匹配数据的时候， 没有做其他操作了。
这样 内for循环会继续下，直到跑完再进行下一轮整体循环。
所以，仅针对这种情形，1对1的或者说我们只需要找到一个匹配项，处理完后我们 应该使用 break 。
我们来看看 加上 break 的一个耗时情况 ：
代码：
public static void main(String[] args) {
List<User> userTestList = getUserTestList();
List<UserMemo> userMemoTestList = getUserMemoTestList();
StopWatch stopWatch = new StopWatch();
stopWatch.start();
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;
}
}
}
stopWatch.stop();
System.out.println("最终耗时"+stopWatch.getTotalTimeMillis());
}
耗时情况：
可以看到 从 2W 多毫秒 变成了 1W 多毫秒， 这个break 加的很OK。
回到我们刚才, 平时需要for 循环 里面再 for 循环 这种方式，可以看到耗时是 2万6千多毫秒。
那如果场景更复杂一定， 是for 循环里面 for循环 多个或者， for循环里面还有一层for 循环 ，那这样代码耗时真的非常恐怖。
那么接下来这个技巧点是 使用map 去优化 ：
代码：
public static void main(String[] args) {
List<User> userTestList = getUserTestList();
List<UserMemo> userMemoTestList = getUserMemoTestList();
StopWatch stopWatch = new StopWatch();
stopWatch.start();
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);
}
}
stopWatch.stop();
System.out.println("最终耗时" + stopWatch.getTotalTimeMillis());
}
看看耗时:
为什么这么显著的效果 ？
这其实就是时间复杂度，for循环嵌套for循环，就好比 循环每一个 user ，拿出 userId 需要在里面的循环从 userMemo list集合里面 按顺序去开盲盒匹配,拿出第一个，看看userId ，拿出第二个，看看userId ，一直找匹配的。
而我们提前对 userMemo list集合 做一次 遍历，转存储在map里面 。
map的取值效率 在多数的情况下是能维持接近 O(1) 的 ， 毕竟数据结构摆着，数组加链表。
相当于拿到userId 想去开盲盒的时候， 根据userId 这个key hash完能直接找到数组里面的索引标记位， 如果底下没链表（有的话O(logN)），直接取出来就完事了。
然后补充一个getNode的代码注释 ：
/**
* Implements Map.get and related methods.
* 这是个 Map.get 的实现 方法
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
// final 写死了 无法更改 返回 Node 传入查找的 hash 值 和 key键
final Node < K, V > getNode(int hash, Object key)
{
// tab 还是 哈希表
// first 哈希表找的链表红黑树对应的 头结点
// e 代表当前节点
// k 代表当前的 key
Node < K, V > [] tab;
Node < K, V > first, e;
int n;
K k;
// 赋值 并过滤 哈希表 空的长度不够的 对应位置没存数据的 都直接 return null
if((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null)
{
// 头结点就 找到了 hash相等值相等 或者 不空的 key 和当前节点 equals
if(first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) return first;
// 头结点不匹配 没找到就 就用 next 找
if((e = first.next) != null)
{
// 是不是红黑树 的
if(first instanceof TreeNode) return ((TreeNode < K, V > ) first).getTreeNode(hash, key);
// 红黑树就直接 调用 红黑树内查找
// 不为空或者没找到就do while 循环
do {
// 当前节点 找到了 hash相等值相等 或者 不空的 key 和当前节点 equals
if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e;
} while((e = e.next) != null);
}
}
return null;
}
按照目前以JDK8 的hash算法，起hash冲突的情况是非常非常少见了。
最恶劣的情况，只有当 全部key 都冲突， 全都分配到一个桶里面去都占用一个位置 ，这时候就是O(n)，这种情景不需要去考虑。
👉 欢迎加入小哈的星球 ，你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利
全栈前后端分离博客项目 2.0 版本完结啦， 演示链接：http://116.62.199.48/ ，新项目正在酝酿中。全程手摸手，后端 + 前端全栈开发，从 0 到 1 讲解每个功能点开发步骤，1v1 答疑，直到项目上线。目前已更新了239小节，累计38w+字，讲解图：1645张，还在持续爆肝中.. 后续还会上新更多项目，目标是将Java领域典型的项目都整一波，如秒杀系统, 在线商城, IM即时通讯，Spring Cloud Alibaba 等等，戳我加入学习，已有1200+小伙伴加入(早鸟价超低)
1. 我的私密学习小圈子~
最近面试BAT，整理一份面试资料《Java面试BATJ通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。
获取方式：点“在看”，关注公众号并回复 Java 领取，更多内容陆续奉上。
PS：因公众号平台更改了推送规则，如果不想错过内容，记得读完点一下“在看”，加个“星标”，这样每次新文章推送才会第一时间出现在你的订阅列表里。
点“在看”支持小哈呀，谢谢啦