从集合中随机选择一个元素

Question

如何从一个集合中随机选取元素？ 我特别希望能在Java中从HashSet或LinkedHashSet中随机选择一个元素。 其他语言的方案也可以考虑。

- Reginaldo

---

你应该指定一些条件来确定这是否是你真正想要的。

• 你将选择多少次随机元素？
• 数据需要存储在 HashSet 还是 LinkedHashSet 中？两者都不支持随机访问。
• HashSet 很大吗？键很小吗？

- David Nehme

Answer 1

int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}

- Khoth

---

如果我的哈希集很大，那么这将是一个相当缓慢的解决方案，因为平均而言，需要(n / 2)次迭代来找到随机对象。 - daniel

如果您的数据存储在一个哈希集合中，且您只需要选择其中一个元素，那么您需要O(n)的时间来完成。如果数据仅存储在哈希集合中，那么无论如何都无法避免这一点。 - David Nehme

这是Java HashSet规范的一个缺陷。在C++中，通常可以直接访问构成hashset的桶(bucket)，这使我们能够更有效地选择随机元素。如果需要随机元素，则值得定义一个自定义哈希集，允许用户查看内部情况。请参见[boost文档][1]了解更多信息。[1] http://www.boost.org/doc/libs/1_43_0/doc/html/unordered/buckets.html - Aaron McDaid

如果在多次访问期间未发生集合的变化，您可以将其复制到数组中，然后进行O(1)访问。只需使用myHashSet.toArray()即可。 - ykaganovich

@ykaganovich 这样做会不会让情况变得更糟，因为集合必须被复制到一个新的数组中？https://docs.oracle.com/javase/7/docs/api/java/util/AbstractCollection.html#toArray%28%29 “即使此集合由一个数组支持，此方法也必须分配一个新的数组”。 - anton1980

Answer 2

有一个相关的“你知道吗”:

在java.util.Collections中，有一些方法可以对整个集合进行洗牌操作：Collections.shuffle(List<?>)和Collections.shuffle(List<?> list, Random rnd)。

- chickeninabiscuit

---

太棒了！这在Java文档中没有交叉引用！就像Python的random.shuffle()一样。 - smci

但这仅适用于列表，即具有 .get() 函数的结构。 - under_the_sea_salad

@bourbaki4481472 绝对正确。这仅适用于扩展 List 接口的集合，而不是 OP 讨论的 Set 接口。 - Thomas

然而，OP希望选择一个元素。对于那个元素来说，洗牌整个列表（并将集合中的所有元素转移到列表中）非常昂贵...如果您有一个列表，可以使用List.get(new Random().nextInt(size))。 - Erk

Answer 3

在Java 8中：

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

- Joshua Bone

---

为什么不使用findFirst().get()而不是orElse()？ - IcedDante

如果没有进行检查就调用get()方法，可能会抛出NoSuchElementException异常。如果可以保证在并发操作中底层元素集合不会被更改（流不会自动原子化），则可以忽略此异常。 - hub

不要使用 set.size()，而是使用 set.size() -1。 - Olivier Faucheux

@Olivier Faucheux，Random（）。nextInt（）中的最大元素不包括在内。因此，set.size（）应该是可以的。 - pyfyc

Answer 4

使用ArrayList和HashMap实现Java的快速解决方案：[元素->索引]。

动机：我需要一个具有RandomAccess属性的项目集，特别是从集合中随机选择一个项目（请参阅pollRandom方法）。在二叉树中进行随机导航不够准确：树不是完美平衡的，这将不会导致均匀分布。

public class RandomSet<E> extends AbstractSet<E> {

    List<E> dta = new ArrayList<E>();
    Map<E, Integer> idx = new HashMap<E, Integer>();

    public RandomSet() {
    }

    public RandomSet(Collection<E> items) {
        for (E item : items) {
            idx.put(item, dta.size());
            dta.add(item);
        }
    }

    @Override
    public boolean add(E item) {
        if (idx.containsKey(item)) {
            return false;
        }
        idx.put(item, dta.size());
        dta.add(item);
        return true;
    }

    /**
     * Override element at position <code>id</code> with last element.
     * @param id
     */
    public E removeAt(int id) {
        if (id >= dta.size()) {
            return null;
        }
        E res = dta.get(id);
        idx.remove(res);
        E last = dta.remove(dta.size() - 1);
        // skip filling the hole if last is removed
        if (id < dta.size()) {
            idx.put(last, id);
            dta.set(id, last);
        }
        return res;
    }

    @Override
    public boolean remove(Object item) {
        @SuppressWarnings(value = "element-type-mismatch")
        Integer id = idx.get(item);
        if (id == null) {
            return false;
        }
        removeAt(id);
        return true;
    }

    public E get(int i) {
        return dta.get(i);
    }

    public E pollRandom(Random rnd) {
        if (dta.isEmpty()) {
            return null;
        }
        int id = rnd.nextInt(dta.size());
        return removeAt(id);
    }

    @Override
    public int size() {
        return dta.size();
    }

    @Override
    public Iterator<E> iterator() {
        return dta.iterator();
    }
}

- fandrew

---

那样做是可行的，但问题是关于Set接口的。这个解决方案强制用户拥有RandomSet的具体类型引用。 - Johan Tidén

我真的很喜欢这个解决方案，但它不是线程安全的，可能会导致Map和List之间的不准确性，因此我会添加一些同步块。 - Kostas Kryptos

@KonstantinosChalkias 内置的集合也不是线程安全的。只有那些名为 Concurrent 的集合才是真正安全的，而使用 Collections.synchronized() 包装的集合则是半安全的。此外，OP 没有提到并发性，因此这是一个有效且好的答案。 - TWiStErRob

此处返回的迭代器不应该能够从 dta 中删除元素（例如，可以通过使用 guava 的 Iterators.unmodifiableIterator 来实现）。否则，在 RandomSet 中使用该迭代器的 AbstractSet 及其父类的默认实现，如 removeAll 和 retainAll，将会破坏您的集合！ - muued

不错的解决方案。如果每个节点包含其子树中节点数量，则实际上可以使用树。然后，在每个节点处基于节点计数计算0..1之间的随机实数，并进行加权3路决策（选择当前节点或进入左侧或右侧子树）。但在我看来，您的解决方案更好。 - Gene

Answer 5

这比已接受答案中的 for-each 循环更快：

int index = rand.nextInt(set.size());
Iterator<Object> iter = set.iterator();
for (int i = 0; i < index; i++) {
    iter.next();
}
return iter.next();

使用for-each循环，每次迭代都会调用Iterator.hasNext()方法，但由于index < set.size()，该检查是不必要的开销。我看到了10-20%的速度提升，但这可能因人而异。(此外，这个方法可以编译，而不需要添加额外的返回语句。)

请注意，此代码（以及大多数其他答案）可以应用于任何集合，而不仅仅是Set。在通用方法中：

public static <E> E choice(Collection<? extends E> coll, Random rand) {
    if (coll.size() == 0) {
        return null; // or throw IAE, if you prefer
    }

    int index = rand.nextInt(coll.size());
    if (coll instanceof List) { // optimization
        return ((List<? extends E>) coll).get(index);
    } else {
        Iterator<? extends E> iter = coll.iterator();
        for (int i = 0; i < index; i++) {
            iter.next();
        }
        return iter.next();
    }
}

- Sean Van Gorder

Answer 6

如果你想用Java实现，你应该考虑将元素复制到某种随机访问集合中（例如ArrayList）。因为，除非你的集合很小，否则访问所选元素将是昂贵的（O（n）而不是O（1））。[注：列表复制也是O（n）] 或者，你可以寻找另一种更符合你要求的Set实现。Commons Collections中的ListOrderedSet看起来很有前途。

- Dan Dyer

---

将内容复制到列表中将花费 O(n) 的时间和 O(n) 的内存，那么为什么选择这样做会比直接从映射中获取更好呢？ - mdma

这取决于你想从这个集合中选择多少次。复制是一次性操作，之后你可以根据需要无限次地从集合中进行选择。如果你只选择一个元素，那么是的，复制不会使事情变得更快。 - Dan Dyer

如果您想要能够重复选择，那么这只是一次操作。如果您希望所选项目从集合中删除，则需要回到O(n)。 - TurnipEntropy

Answer 7

在Java中：

Set<Integer> set = new LinkedHashSet<Integer>(3);
set.add(1);
set.add(2);
set.add(3);

Random rand = new Random(System.currentTimeMillis());
int[] setArray = (int[]) set.toArray();
for (int i = 0; i < 10; ++i) {
    System.out.println(setArray[rand.nextInt(set.size())]);
}

- Jorge Ferreira

---

你的答案是正确的，但由于set.toArray( )部分不够高效。 - Clue Less

你应该将 "toArray" 方法移到循环外面。 - David Nehme

Answer 8

List asList = new ArrayList(mySet);
Collections.shuffle(asList);
return asList.get(0);

- Ben Noland

---

这太低效了。你的ArrayList构造函数在提供的集合上调用.toArray()方法。ToArray（在大多数标准集合实现中）会遍历整个集合并逐个填充数组。然后你会打乱列表，这会将每个元素与随机元素交换。你最好直接在集合上迭代到一个随机元素。 - Chris Bode

Answer 9

这与被接受的答案（Khoth）完全相同，但删除了不必要的size和i变量。

    int random = new Random().nextInt(myhashSet.size());
    for(Object obj : myhashSet) {
        if (random-- == 0) {
            return obj;
        }
    }

尽管消除了前面提到的两个变量，上述解决方案仍然是随机的，因为我们依赖于随机数（从随机选择的索引开始）在每次迭代中向 0 递减。

- Jason Hartley

---

第三行也可以是 if (--random < 0) {，其中 random 达到 -1。 - Salvador

Answer 10

Java 8+ 流：

    static <E> Optional<E> getRandomElement(Collection<E> collection) {
        return collection
                .stream()
                .skip(ThreadLocalRandom.current()
                .nextInt(collection.size()))
                .findAny();
    }

基于Joshua Bone的答案，但稍作改动：

• 为了在并行操作中稍微提高性能，忽略了Streams元素的顺序
• 使用当前线程的ThreadLocalRandom
• 接受任何集合类型作为输入
• 返回提供的Optional而不是null

- hub