如何从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

打乱集合意味着其中有一些已定义的元素顺序，因此可以重新排序元素。 HashSet 不是一个有序的集合，因为里面没有元素的顺序（或者更确切地说，排序的细节不会暴露给用户）。因此，在实施方面，洗牌 HashSet.

没有多大意义

您可以做的是将 set 中的所有元素添加到 ArrayList 中，将其打乱并得到结果。

List<String> usersList = new ArrayList<String>(users);
Collections.shuffle(usersList);
// get 100 elements out of the list

Answer 2

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

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 来选择未来的元素，但在同时增加概率，减少d。最初，您将有 100/10000 的机会选择第一个元素。如果您决定采用该元素，您将有 99/9999 的机会选择第二个元素；如果你不选第一个，你会有更好的 100/9999 机会选择第二个元素。数学计算得出，最终每个元素都有 100/10000 的机会被选中用于输出。

Answer 3

java.lang.HashSet 有顺序，因此您不能洗牌。如果您必须使用 Sets，您可能会遍历 Set 并在随机位置停止。

伪代码：

Set randomUsers = new HashSet<String>();
Random r = new Random();
Iterator it = users.iterator(); 
numUsersNeeded = 100;
numUsersLeft = users.size();
while (it.hasNext() && randomUsers.size() < 100) {
  String user = it.next();
  double prop = (double)numUsersNeeded / numUsersLeft;
  --numUsersLeft;
  if (prop > r.nextDouble() && randomUsers.add(user)) { 
    --numUsersNeeded;
  }
}

您可能会重复此操作，因为无法保证您获取 100 个元素。

如果内存没有问题，您可以创建一个数组并随机选择 100 个元素：

伪代码二：

Object userArray[] = user.toArray();
Set<String> randoms = new HashSet<String>();
while(randoms.size() != 100) {
  int randomUser = userArray[new Random().nexInt(10000)];
  randoms.add(randomUser);
}

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

How to get 100 random elements from HashSet in Java?

java

random

set

hashset