数据集合分组巧排

在编程开发中，List 与 Map 可谓是 Java 集合体系中的左膀右臂，高频的应用于工程中的各个角落，今天就让我们进一步探究其中的门道。

1. 循环优化

List 对数据集合提供了丰富的操作方式，而 Map 则对性能优化发挥了举足轻重的作用，最经典的案例即通过 Map 解构嵌套循环，实现数量级的时间复杂度缩减。

让我们通过示例进行演示，假设需要获取两个对象集合中同名的元素，最简单的方式就是分别遍历两个集合并进行元素匹配，如下述代码：

public static void main(String[] args) {
    List<User> list1 = getUserList1(); 
    List<User> list2 = getUserList2();

    List<User> commonList = new ArrayList<>();
    for (User i : list1) {
        for (User j : list2) {
            // 匹配同名元素
            if (Objects.equals(i.getName(), j.getName())) {
                commonList.add(i);
            }
        }
    }
    System.out.println("Common element: " + commonList);
}

可以看到，在上述的实现方式中代码的时间复杂度为 O(n^2)，若此时 list1 与 list2 集合数量达到一定量级时，显然性能将不尽人意。

那么应该如何改进呢？方式其实很简单，通过 Map 的哈希机制便可将时间复杂度降至 O(n)，改造上述的示例得到下述结果：

public static void main(String[] args) {
    List<User> list1 = getUserList1(); 
    List<User> list2 = getUserList2();
    // 构建 Map 集合
    Map<String, User> userMap = new HashMap<>();
    list1.forEach(it -> userMap.put(it.getName(), it))

    List<User> commonList = new ArrayList<>();
    for (User user : list2) {
        String username = user.getName();
        if (!userMap.contains(username)) {
            // 不存在跳过
            continue;
        }

        commonList.add(userMap.get(username))
    }
    System.out.println("Common Friends: " + commonFriends);
}

2. 集合排序

Map 除了上述提到循环优化功能外，其数据分组在日常开发中同样频繁涉及，在 stream 流处理中更使提供了 groupingBy() 简化这一过程。

但我们都知道 HashMap 基于哈希与链表/红黑树实现，集合内元素并无先后次序，因此想对其排序则需要另辟蹊径。LinkedHashMap 结构则刚好满足了这一需求场景，其元素存储顺序按照存入的先后进行排序，虽性能无法取得 HashMap 同样的效果，但其仍拥有哈希的特性。

如此一来基本思路就确定了，只要遍历 HashMap 集合后按特定顺序存入 LinkedHashMap，即可获得一个有序的 Map 集合。

那就只剩下一个问题？如何确认元素优先级像标题所提到的实现巧排？

回到数据本身，通过分组后的数组通常 key 为某类唯一标识符，而每个标识符都有其所对应的类型，这个每个类型又都有各自的优先级。此优先级即用于确定 Map 中的每个元素的优先级。

这里想分享的一个技巧就是通过 List 定义类型集合，总所周知 List 为有序集合，那通过 indexOf() 获取每个元素的下标即可作为其优先级。因此，只需要对应的类型优先级集合以及唯一标识和类型的映射关系，即可实现 Map 集合的元素排序。

将上述提到的思路转化为代码，即可得到下述排序算法：

// 类型枚举
public enum Type {
    A, B, C, MAX;
}

private void groupSortData(List<Type> priority, 
                           List<User> userList,
                           Map<String, Type> typeMap) {
    // 分组
    Map<String, List<User>> userMap = userList.stream()
            .collect(Collectors.groupingBy(User::getName));
    // 排序
    LinkedHashMap<String, List<User>> sortMap = userMap.entrySet()
            .stream()
            .sorted((e1, e2) -> {
                // 获取数据类型
                Type type1 = typeMap.getOrDefault(e1.getKey(), Integer.MAX);
                Type type2 = typeMap.getOrDefault(e2.getKey(), Integer.MAX);
                
                // 根据类型取优先级
                int index1 = priority.indexOf(type1);
                int index2 = priority.indexOf(type2);
                return Integer.compare(index1, index2);
            })
            .collect(Collectors.toMap(
                    Map.Entry::getKey,
                    Map.Entry::getValue,
                    (r1, r2) -> r1,
                    // 使用 LinkedHashMap 有序集合
                    LinkedHashMap::new
            ));

    // 打印输出
    System.out.println(sortMap);
}

下面通过示例验证一下这个思路是否可行，通过有序集合 List 定义优先级集合 priority，元素下标越小则优先级越高。

public void demo() {
    // 优先级映射
    Map<String, Type> typeMap = new HashMap<>();
    typeMap.put("Alex", Type.A);
    typeMap.put("Beth", Type.B);
    typeMap.put("Jack", Type.C);

    // 定义优先级
    List<Type> priority = List.of(
        Type.C, Type.A, Type.B, Type.MAX
    );

    // 构造数据
    List<User> userList = new ArrayList<>();
    userList.add(new User("Alex", 1));
    userList.add(new User("Alex", 11));
    userList.add(new User("Beth", 2));
    userList.add(new User("Beth", 22));
    userList.add(new User("Jack", 3));
    userList.add(new User("Jack", 33));

    // 排序
    this.groupSortData(priority, userList, typeMap);
}

运行上述示例，在控制台输出下述结果，可以看到结果正是按照所定义的 C > B > A 次序进行排序。

{
    Jack=[User{id=3}, User{id=33}], 
    Alex=[User{id=1}, User{id=11}],
    Beth=[User{id=2}, User{id=22}]
}