集合随机取数算法

默认 JDK 中提供了丰富的集合容器，每个都足以让人眼花缭乱，各自在适用于不同的场景之下。

在许多的业务中，常常会涉及到随机取数的需求场景，最为典型的莫过于抽奖，更进一步的如题库选题等等。

面对此类场景基本思路大概分为两类：使用无序集合或打乱有序集合。

1. 无序集合

让我们从最简单的无序集合开始，在 JDK 中最为基础的无序集合莫过于 Set 与 Map。

如常用的 HashSet 与 HashMap 容器中，其并不以存入的顺序排列，而是以元素的哈希值为依据。

以 HashSet 为例，下述示例以倒叙存入容器，但输出的结果并非 [5, 4, 3, 2, 1] 而是 [1, 2, 3, 4, 5]。

public void demo() {
    Set<Integer> set = new HashSet<>();
    for (int j = 5; j > 0; j--) {
        set.add(j);
    }

    System.out.println(set);
}

或许你可能也发现了，这类随机其实是一种伪随机。容器中元素不以存入的顺序排列，但仍然依照某类特地规则，如此处即以哈希值为排列依据。

因此，即便对于无序集合，实现随机访问通常配合 Random 等随机工具类。

如下述示例即利用 stream 与 Random 实现随机元素取值：

 public void demo() {
    Set<Integer> set = Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9);

    for (int i = 0; i < 5; i++) {
        int index = new Random().nextInt(set.size() - 1);
        System.out.println(set.stream().skip(index).findFirst().get());
    }
}

2. 洗牌算法

针对有序集合的随机取数，最简单方式即打散顺序后访问，实现访问相同位置得到不同的结果。

在 JDK 中自带了 java.util.Collections#shuffle 方法，基于 Fisher-Yates 算法实现打乱集合顺序。

针对 ArrayList 容器为例，其实现于 RandomAccess 支持随机访问，底层数据结构为数组即连续的存储空间。从实现源码可以看出，实现逻辑并不复杂，遍历数组并通过 Random 类随机交换两个位置上的元素值从而实现打印的效果。

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--) {
            swap(list, i-1, rnd.nextInt(i));
        }
    } else {
        ...        
    }
}

public static void swap(List<?> list, int i, int j) {
    final List l = list;
    l.set(i, l.set(j, l.get(i)));
}

完成容器元素的顺序打印之后，实现随机取值的则通过 get() 访问即可，每次洗牌后的集合顺序都并会相同，访问同一位置的元素返回的值也将不一样。

若要批量随机取数，则可对洗牌后的集合通过 subList() 取子集合实现。

3. 随机取数

在 shuffle() 洗牌方法中，可以看出算法的时间复杂为 O(n)，那是否有更优的方式。

以实际业务场景为例，系统中存在一个 1w 大小的题库，每次需要从中抽取 20 道不重复题目。若采用 shuffle 方式显然每次都需对原集合打乱，造成一定的性能浪费。

因此，对于一个大小为 m 的容器，且需随机取 n 个元素，若 m >> n 则显然洗牌算法并不适用。

对于此类场景，最合适的方案以利用数组支持随机访问的特性，变量容器身上聚焦于抽取的元素上。

如下述代码示例即基于 Random 实现了有序集合的随机取 5 个数，而时间复杂度则无关容器大小，只与取数数量正相关。

public void demo2() {
    List<Integer> list = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9);

    Set<Integer> result = new HashSet<>();
    while (result.size() < 5) {
        int index = new Random().nextInt(list.size() - 1);
        Integer ele = list.get(index);
        if (result.contains(ele)) {
            // 存在则跳过
            continue;
        }

        result.add(ele);
    }
    System.out.println(result);
}