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

Question

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

4

我有一个HashSet，其中有10000个元素。我想从这个HashSet中提取随机的100个元素。所以我想我可以在集合上使用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个随机元素？

- user1950349

4

您的代码无法编译，因为Collections.shuffle需要一个列表（List）作为参数。因此，请尝试从您的集合（Set）创建一个List，然后对该列表进行随机排序（shuffle）。 - Robin Krahl

对 users.toArray() 的结果进行洗牌。 - pjs

3个回答

6

对集合进行洗牌意味着其中有一些定义好的元素顺序，所以可以重新排序。 HashSet 不是一个有序的集合，因为里面的元素没有顺序（或者说排序的细节不会暴露给用户）。因此，在实现上洗牌 HashSet 没有太多意义。

你可以做的是将所有元素从你的 set 添加到 ArrayList 中，然后对其进行洗牌并获取结果。

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

- Dmitry Zaytsev

那你的意思是我应该将一个Set转换成List，然后再这么做吗？ - user1950349

@user1950349，chepner 给出的答案似乎能够产生正确的结果。如果用户数量较少，我建议将 set 转换为 List。否则，请考虑 chepner 的解决方案。 - Dmitry Zaytsev

-1

java.lang.HashSet具有顺序，因此您不能对集合进行shuffle操作。如果必须使用Set，可以迭代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个元素：

伪代码 II：

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

- TobiSH

1

那样就不会是一个均匀分布了 - 最后的元素被选中的概率较小。 - Dmitry Zaytsev

你是对的。感谢你指出这一点。我调整了第一个代码，使第一个元素选择的概率更低。据我所见，现在我们应该有一个均匀分布。 - TobiSH

你的第二个伪代码也不正确 - 它可能会连续选择数组中的同一个元素。这将导致输出集合中少于100个元素。 - Dmitry Zaytsev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chepner · Accepted Answer

不需要建立一个新的列表，你可以实现以下算法：

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的机会被选中输出。