我们可以安全地对 Java Collections shuffle(List<?>, Random) 方法做出哪些假设？
What assumptions can we safely make about the Java Collections shuffle(List<?>, Random) method?
所以我正在研究集合随机播放方法，并试图列出我们 运行 时可以确保和不能确保的内容的列表。我提出了一些明显的案例如下：
- 给定的列表在洗牌后将包含与之前相同的元素
- 运行使用该方法后列表可能相同也可能不同（您最终可能会得到相同的元素顺序）
- 该方法将在线性时间内 运行（我认为这是真的，但不是 100% 肯定）。
这个列表是总结还是我遗漏了一些可能的情况？
- 是的（以及更多-列表本身将保持相同的对象）
- 正确，总是有很小的机会随机获得完全相同的元素顺序（对于小列表来说不是那么小）
- 这是基于实现的，但至少在 java 7 之前它是线性的（并且不太可能是它改变的原因）
official documentation of Collections.shuffle has a lot to say about what will happen. The list will be shuffled using what seems to be the Fisher-Yates shuffle algorithm，它（假设随机访问在 O(1) 中可用）运行时间为 O(n) 和 space O(1)。如果随机访问不可用，该实现将使用 space O(n)。假设底层随机源是完全无偏的，任何特定排序发生的概率是相等的（也就是说，你得到可能排列的 uniformly-random 分布）。
所以，回答你的问题：
- 该列表将包含相同的元素。
- 它们的顺序可能不同，但有一个 1 / n！机会比他们的顺序相同。
- 运行时间为 O(n)，space 用法为 O(1) 或 O(n)，具体取决于您的列表是否支持随机访问。
所以我正在研究集合随机播放方法，并试图列出我们 运行 时可以确保和不能确保的内容的列表。我提出了一些明显的案例如下：
- 给定的列表在洗牌后将包含与之前相同的元素
- 运行使用该方法后列表可能相同也可能不同（您最终可能会得到相同的元素顺序）
- 该方法将在线性时间内 运行（我认为这是真的，但不是 100% 肯定）。
这个列表是总结还是我遗漏了一些可能的情况？
- 是的（以及更多-列表本身将保持相同的对象）
- 正确，总是有很小的机会随机获得完全相同的元素顺序（对于小列表来说不是那么小）
- 这是基于实现的，但至少在 java 7 之前它是线性的（并且不太可能是它改变的原因）
official documentation of Collections.shuffle has a lot to say about what will happen. The list will be shuffled using what seems to be the Fisher-Yates shuffle algorithm，它（假设随机访问在 O(1) 中可用）运行时间为 O(n) 和 space O(1)。如果随机访问不可用，该实现将使用 space O(n)。假设底层随机源是完全无偏的，任何特定排序发生的概率是相等的（也就是说，你得到可能排列的 uniformly-random 分布）。
所以，回答你的问题：
- 该列表将包含相同的元素。
- 它们的顺序可能不同，但有一个 1 / n！机会比他们的顺序相同。
- 运行时间为 O(n)，space 用法为 O(1) 或 O(n)，具体取决于您的列表是否支持随机访问。