Java的Collections.shuffle在做什么？

Question

最近我发现自己需要确保列表不是有序的。Hibernate很好地返回了完美的有序列表。愚蠢的Hibernate，没有读懂我的意思。

我查看了Java API，它告诉我其shuffle方法会这样做：

使用默认的随机源随机排列指定的列表。

作为一个好奇的人，我想知道这到底是什么意思。有没有数学课程可以让我学习这个？我能看到代码吗？Java，你在对我的ArrayList做什么？！？

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

- Stephano

---

+1 是因为认识到提出这个问题的原因是出于好奇心，而不是因为在使用方法之前知道它的所有细节很重要。 - Tyler

在 Bloch & Gafter 的《Java Puzzlers》中有一些关于 shuffle 的讨论。 - Tom Hawtin - tackline

Answer 1

是的，你可以查看代码；它基本上执行的是费雪-耶茨洗牌算法。以下是代码（感谢OpenJDK和开源精神）：

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]);
        }
    }
}

交换方法（swap method）：

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

- C. K. Young

---

啊，没错，OpenJDK。好的，“我能看到代码吗”的问题有点傻 :）。谢谢。 - Stephano

是的！:-) 所以，现在您只需要了解一下 Fisher-Yates 洗牌算法，然后就准备好了。:-) - C. K. Young

Answer 2

Collections JavaDoc中提供了有关使用shuffle方法的一些信息。

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

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

- Bill the Lizard

---

它是如何获取这个随机整数的？ - Stephano

当“preceding”是非严格类型时（即，每次迭代都可能导致一个项目与自身交换）。 :-P - C. K. Young

@Stephano：如果你不指定一个“Random”对象，它将使用“new java.util.Random()”。 （这没有明确说明; 这只是OpenJDK版本的工作方式。） - C. K. Young

@Chris：谢谢，我一直在想这个问题。我在回答的末尾添加的那一部分纯属我个人的猜测。 - Bill the Lizard