java - Java 如何从 HashSet 中获取 100 个随机元素？

Question

我有一个 HashSet，其中有 10000 个元素。我想从该 HashSet 中随机提取 100 个元素。所以我想我可以在 set 上使用 shuffle，但它不起作用。

Set<String> users = new HashSet<String>();

// for randomness, but this doesn't work
Collections.shuffle(users, new Random(System.nanoTime()));  

// and use for loop to get 100 elements

我现在不能使用 shuffle，有没有其他最好的方法从 Java 中的 HashSet 中获取 100 个随机元素？

Answer 1

无需构建新列表，您可以实现以下算法:

n = 100
d = 10000  # length(users)
for user in users:
    generate a random number p between 0 and 1
    if p <= n / d:
       select user
       n -= 1
    d -= 1

当您遍历列表时，您会降低通过减少 n 来选择 future 的元素，但在同时通过减少 d 来增加概率。原来，您将有 100/10000 的机会选择第一个元素。如果您决定采用该元素，您将有 99/9999 的机会选择第二个元素；如果你不拿第一个，你会有更好的 100/9999 机会选择第二个元素。数学计算结果表明，最终每个元素都有 100/10000 的机会被选中用于输出。