for 循环嵌套 for 循环，你需要懂的代码性能优化技巧！

前言本篇分析的技巧点其实是比较常见的，但是最近的几次的代码评审还是发现有不少兄弟没注意到。

所以还是想拿出来说下。

正文是个什么场景呢？

就是 for 循环 里面还有 for 循环， 然后做一些数据匹配、处理 这种场景。

我们结合实例代码来看看。

场景示例：

比如我们现在拿到两个 list 数据 ，一个是 User List 集合 ；另一个是 UserMemo List 集合；

我们需要遍历 User List ，然后根据 userId 从 UserMemo List 里面取出 对应这个 userId 的 content 值，做数据处理。

代码 User.java ：

import lombok.Data;

@Datapublic class User {private Long userId;private String name;}代码 UserMemo.java ：

import lombok.Data;

@Datapublic 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 代表当前的 keyNode<K,V>[] tab; Node<K,V> first, e; int n; K k;// 赋值 并过滤 哈希表 空的长度不够的 对应位置没存数据的 都直接 return nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 头结点就 找到了 hash 相等值相等 或者 不空的 key 和当前节点 equalsif (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 和当前节点 equalsif (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），这种情景不需要去考虑。