Java的 Collections.shuffle在做什么？

shuffle collections java

2022-09-01 03:09:28

我最近发现自己需要确保我的列表不按顺序排列。冬眠很好，可以完美地返回它。傻傻的冬眠，不读懂我的心思。

我看了一下我的Java API，它告诉我它的洗牌方法就是这样做的：

使用默认的随机性源随机置换指定的列表。

作为好奇的乔治，我想知道这到底意味着什么。有没有一门数学课程我可以学习这个？我可以看到代码吗？Java，你对我的ArrayList做了什么?!?!?

更具体地说，这里使用了哪些数学概念？

答案 1

是的，您可以查看代码;它基本上做了一个Fisher-Yates洗牌。这里是（感谢OpenJDK，以及开源的yay：-P）：

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 {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

交换方法：

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}

答案 2

Collections JavaDoc 提供了一些关于所用 shuffle 方法的信息。

此实现从最后一个元素到第二个元素向后遍历列表，重复将随机选择的元素交换到“当前位置”。元素是从列表中从第一个元素到当前位置（包括当前位置）的部分中随机选择的。

因此，它从末尾开始，向后移动列表。在每个元素处，它停止并将当前元素与列表中的前一个元素交换。在这种情况下，“随机性的默认源”可能是使用默认种子创建的 Random 对象。