掌握这个优化双循环的技巧 效率猛增80%

用map来优化双循环 节目详情部分

在微服务中的项目中，经常会遇到这种的业务：要查询两个表中公共的数据，比如一个表是查询用户信息，其中包含部门编号，另一个表是查询部门信息。这两个表是在两个服务中，而现在要得到每个用户所在的部门名称，通常实现的方式是进行双循环来查询数据 这里举个示例：

用户

@Data
public class TestUser {

    private long id;
    
    private String name;
    
    private long deptId;
}

用户集合为10万

public static List<TestUser> getTestUserList(){
    List<TestUser> testUsers = new ArrayList<>(100000);
    for (long i = 0; i < 100000; i++) {
        TestUser testUser = new TestUser();
        testUser.setId(i);
        testUser.setName("用户-" + i);
        testUser.setDeptId(i);
        testUsers.add(testUser);
    }
    return testUsers;
}

部门

@Data
public class TestDept {
    
    private long id;
    
    private String name;
}

部门集合为5万

public static List<TestDept> getTestDeptList(){
    List<TestDept> testDepts = new ArrayList<>(50000);
    for (long i = 0; i < 50000; i++) {
        TestDept testDept = new TestDept();
        testDept.setId(i);
        testDept.setName("部门-" + i);
        testDepts.add(testDept);
    }
    return testDepts;
}

常规的双循环来查询

这里使用最常见的方法，使用双循环来匹配数据，第一层循环为用户集合，然后每次循环用户集合中的元素时，再循环部门集合

public static void run1(){
    List<TestUser> testUserList = getTestUserList();
    List<TestDept> testDeptList = getTestDeptList();
    long start = System.currentTimeMillis();
    for (TestUser testUser : testUserList) {
        long deptId = testUser.getId();
        String userName = testUser.getName();
        for (TestDept testDept : testDeptList) {
            long id = testDept.getId();
            String name = testDept.getName();
            if (deptId == id) {
                System.out.println("用户名为"+userName+" 的部门信息为:" + name);
            }
        }
    }
    System.out.println("执行1 耗时为：" + (System.currentTimeMillis() - start) + " ms");
}

执行耗时

执行1 耗时为：21995 ms

优化

其实一眼就知道耗时是在第二个循环中，在第二次循环中如果匹配到了的话完全可以不用再接着往下继续循环了，比如说用户1匹配到了部门1，那么就不用再循环部门集合了，直接用终止就行了，那么如果终止呢？就是用break。我们用上试试

使用break处理双循环

public static void run2(){
    List<TestUser> testUserList = getTestUserList();
    List<TestDept> testDeptList = getTestDeptList();
    long start = System.currentTimeMillis();
    for (TestUser testUser : testUserList) {
        long deptId = testUser.getId();
        String userName = testUser.getName();
        for (TestDept testDept : testDeptList) {
            long id = testDept.getId();
            String name = testDept.getName();
            if (deptId == id) {
                System.out.println("用户名为"+userName+" 的部门信息为:" + name);
                break;
            }
        }
    }
    System.out.println("执行2 耗时为：" + (System.currentTimeMillis() - start) + " ms");
}

执行耗时

执行2 耗时为：7820 ms

可以看到效果十分的显著啊！从21995 ms 直接 降到了 7820 ms

但我们再仔细的想想看，这种使用break的方式是适合第二个循环次少的情况下，比如说用户1，第二个循环第1次就找到了，就省去了49999次的循环

但是，如果确实是要循环次数多的情况呢？举一个极端的例子 ：比如说用户50000，真的就得循环部门50000次找到部门最后一个元素了才能匹配到，前面还得循环那么多次

那么有没有什么办法，能尽量的始终避免第二次的循环这么多次呢？这里先不急往下看，小伙伴先仔细想想常用的集合的时间复杂度各是多少？这个知识点其实挺重要的，确定了在什么场景下使用哪种数据结构从而采用哪种集合

如果小伙伴比较熟悉的话，相信心里应该是有答案了，其实就是最常用的Map结构！这里先不着急解释使用Map的原因，先直接看执行的效果到底怎么样

使用Map处理双循环

public static void run3(){
    List<TestUser> testUserList = getTestUserList();
    List<TestDept> testDeptList = getTestDeptList();
    Map<Long, TestDept> testDeptMap = 
            testDeptList.stream().collect(Collectors.toMap(TestDept::getId, testDept -> testDept, (v1, v2) -> v2));
    long start = System.currentTimeMillis();
    for (TestUser testUser : testUserList) {
        long deptId = testUser.getId();
        String userName = testUser.getName();
        
        TestDept testDept = testDeptMap.get(deptId);
        if (Objects.nonNull(testDept)) {
            String name = testDept.getName();
            System.out.println("用户名为"+userName+" 的部门信息为:" + name);
        }
    }
    System.out.println("执行3 耗时为：" + (System.currentTimeMillis() - start) + " ms");
}

解释Map转化的流程

testDeptList.stream().collect(Collectors.toMap(TestDept::getId, testDept -> testDept, (v1, v2) -> v2));

• 这行是jdk8的新特性，将testDeptList转为stream流后，以dept的id为key，dept对象为value
• (v1, v2) -> v2 意思是当dept的id出现重复时，取后面的值作为value

执行耗时

执行3 耗时为：161 ms

这回更牛逼 直接降到161ms ! 从21995 ms 直接 降到了 161ms 这是什么量级的优化！