使用 randomElement() 方法编写 Set 实现

Question

我正在尝试编写一个 Set 的实现，它有一个额外的方法 randomElement()，其中 returns 从 Set 中随机选择一个元素。我已经基于 HashSet 实现了快速 contains() 方法。我还使用了 ArrayList，因此 randomElement() 方法也是 O(1) - 对于 ArrayList，您所要做的就是选择一个随机索引。

这是我的代码。

public final class RandomChoiceSet<E> extends AbstractSet<E> {

    private final List<E> list = new ArrayList<>();
    private final Set<E> set = new HashSet<>();
    private final Random random = new Random();

    public RandomChoiceSet() {}

    public RandomChoiceSet(Collection<? extends E> collection) {
        addAll(collection);
    }

    public E randomElement() {
        return list.get(random.nextInt(list.size()));
    }

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

    @Override
    public boolean contains(Object o) {
        return set.contains(o);
    }

    @Override
    public void clear() {
        list.clear();
        set.clear();
    }

    @Override
    public boolean add(E e) {
        boolean result = set.add(e);
        if (result)
            list.add(e);
        return result;
    }

    @Override
    public boolean remove(Object o) {
        boolean result = set.remove(o);
        if (result)
            list.remove(o);
        return result;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            private final Iterator<E> iterator = list.iterator();
            private E e;

            @Override
            public boolean hasNext() {
                return iterator.hasNext();
            }

            @Override
            public E next() {
                return e = iterator.next();
            }

            @Override
            public void remove() {
                iterator.remove();
                set.remove(e);
            }
        };
    }
}

维护 List 和 Set 的缺点是它使 remove() 方法 O(n) 因为必须在 ArrayList 首先，然后所有其他元素都必须沿着一个地方移动。所以我想知道是否可以写这样一个 Set，其中所有五个操作 size()、contains()、add()、remove() 和 randomElement() O(1)?

Answer 1

我唯一能想到的就是用从您的元素映射到它在 arrayList 中的位置的 HashMap 替换您的集合。大小、包含、添加和随机将是相同的。对于删除，您将执行以下操作：

Find the element from the HashMap
Retrieve it's position in the arrayList
Remove the element from the HashMap
Swap the deleted element with the last element in the array
Modify the swapped element position in the HashMap
Delete the last element from the array //Now this is O(1)

这项工作的成功之处在于您不需要在阵列中有任何特定的顺序，您只需要一个随机访问存储，因此只要您保持同步，更改顺序或数据就不会造成任何问题用你的哈希图。

Answer 2

我认为您需要 HashMap 的自定义实现，因为它需要细粒度控制。随机选择一个桶很容易，你可以在你的桶中使用 ArrayLists 来随机访问。

为了清楚起见，您将实施经典的 HashMap，但不是在每个存储桶中使用 LinkedList，而是使用 ArrayList。选择一个随机元素就像 :

一样简单

在 0 和 nbBuckets

rd0

在 0 和 buckets[rd0].size()

rd1

Answer 3

这是一个功能实现，遵循 Amr 的解决方案。即使 Iterator 的 remove() 方法也有效，因为元素总是从后面的位置换入。

public final class RandomChoiceSet<E> extends AbstractSet<E> {

    private final List<E> list = new ArrayList<>();
    private final Map<E, Integer> map = new HashMap<>();
    private final Random random = new Random();

    public RandomChoiceSet() {}

    public RandomChoiceSet(Collection<? extends E> collection) {
        addAll(collection);
    }

    public E randomElement() {
        return list.get(random.nextInt(list.size()));
    }

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

    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    @Override
    public void clear() {
        list.clear();
        map.clear();
    }

    @Override
    public boolean add(E e) {
        if (map.containsKey(e))
            return false;
        map.put(e, list.size());
        list.add(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        Integer currentIndex = map.get(o);
        if (currentIndex == null)
            return false;
        int size = list.size();
        E lastE = list.get(size - 1);
        list.set(currentIndex, lastE);
        list.remove(size - 1);
        map.put(lastE, currentIndex);
        map.remove(o);
        return true;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            private int index = 0;

            @Override
            public boolean hasNext() {
                return index < list.size();
            }

            @Override
            public E next() {
                return list.get(index++);
            }

            @Override
            public void remove() {
                RandomChoiceSet.this.remove(list.get(--index));
            }
        };
    }
}

编辑

我想得越多，这个 Set 实现就越有用。虽然我没有在上面的代码中这样做，但你可以包含一个 get() 方法来按索引获取元素。这不仅比从 Set（例如 set.iterator().next() 或 set.stream().findAny().get()）获取任何元素的其他方法更好，而且它使您能够使用显式索引遍历集合。

int n = set.size();
for (int i = 0; i < n; i++) {
    Object o = set.get(i);
    // do something with o.
}

我没有做适当的基准测试，但像这样迭代 Set 似乎比使用 for each 循环迭代 HashSet 快几倍。显然没有检查并发修改，这是一个比 HashSet 更耗内存的 Set 实现（虽然不像 LinkedHashSet 那样耗内存），但总的来说我觉得挺有意思的。

Answer 4

这是一个完美的例子，说明了为什么 Collections 接口应该有一个 getRandom() 方法，以及为什么它是 API 中一个基本缺失的功能。 HashSet 的 getRandom() 实现只会调用它的私有 HashMap getRandom() 方法等等，直到数据表示是可索引或可迭代的，此时应该实现 getRandom() 逻辑。

基本上，这种 getRandom() 方法的复杂性会根据底层实现而有所不同。但是由于在引擎盖下所有数据最终都必须存储为数组或链表，因此由于没有集合感知 getRandom()，很多优化被搁置了。

想一想，什么是Collection？想想我可以从现实世界中的集合中检索随机元素吗？是的，所以它应该在适当的 OO 代码中。

然而它并没有，因此如果您无力构建自己的 class.[=，您将不得不迭代 hashSet 中的项目并返回 random.nextInt(size()) 元素。 17=]

如果您有能力构建自己的实现（这似乎是您的情况），那么您的建议是一种公平的方法，但是我不明白为什么要实现自己的匿名迭代器，这应该没问题。

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

使用 randomElement() 方法编写 Set 实现

Writing a Set implementation with a randomElement() method

java

collections

set

time-complexity