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

Question

我有一个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个随机元素？

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来减少选择未来元素的概率,但同时通过减少d来增加概率.最初,您有100/10000的机会选择第一个元素.如果您决定采用该元素,您将有99/9999的机会选择第二个元素; 如果你不拿第一个,你将有更好的100/9999选择第二个元素的机会.数学计算结果是,最终,每个元素都有100/10000的机会被选中作为输出.

Answer 2

对集合进行混洗意味着内部存在一些已定义的元素顺序,因此可以对元素进行重新排序.HashSet不是有序的集合,因为内部没有元素的顺序(或者更确切地说,订购的细节不会暴露给用户).因此实施起来,洗牌没有多大意义HashSet.

你可以做的是添加你的所有元素,set将其ArrayList洗牌并获得结果.

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