深圳网站建设..,软件开发外包,品牌设计方案,国外炫酷网站前言 本篇分析的技巧点其实是比较常见的#xff0c;但是最近的几次的代码评审还是发现有不少兄弟没注意到。
所以还是想拿出来说下。 正文 是个什么场景呢#xff1f; 就是 for循环 里面还有 for循环#xff0c; 然后做一些数据匹配、处理 这种场景。 我们结合实例代码来…前言 本篇分析的技巧点其实是比较常见的但是最近的几次的代码评审还是发现有不少兄弟没注意到。
所以还是想拿出来说下。 正文 是个什么场景呢 就是 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 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;} 先看平时大家不注意的时候可能会这样去写代码处理 ps 其实数据量小的话其实没多大性能差别不过我们还是需要知道一些技巧点。 代码 public static void main(String[] args) {ListUser userTestList getUserTestList();ListUserMemo 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) {ListUser userTestList getUserTestList();ListUserMemo 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) {ListUser userTestList getUserTestList();ListUserMemo userMemoTestList getUserMemoTestList();StopWatch stopWatch new StopWatch();stopWatch.start();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);}}stopWatch.stop();System.out.println(最终耗时 stopWatch.getTotalTimeMillis());}
看看耗时: 为什么 这么显著的效果 这其实就是时间复杂度
for循环嵌套for循环 就好比 循环每一个 user 拿出 userId
需要在里面的循环从 userMemo list集合里面 按顺序去开盲盒匹配, 拿出第一个看看userId 拿出第二个看看userId 一直找匹配的。
而我们提前对 userMemo list集合 做一次 遍历转存储在map里面 。 map的取值效率 在多数的情况下是能维持接近 O1 的 毕竟数据结构摆着数组加链表。 相当于拿到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 NodeK,V getNode(int hash, Object key) {
// tab 还是 哈希表
// first 哈希表找的链表红黑树对应的 头结点
// e 代表当前节点
// k 代表当前的 keyNodeK,V[] tab; NodeK,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 ((TreeNodeK,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 都冲突 全都分配到一个桶里面去都占用一个位置 这时候就是On这种情景不需要去考虑。 好了该篇就到这。
