用randomElement（）方法编写Set实现 [英] Writing a Set implementation with a randomElement() method

问题描述

我试图写一个 Set 的实现，它有一个附加的方法 randomElement（）随机从设置。我已经基于 HashSet 的实现基于快速的 contains（）方法。我还使用 ArrayList ，使 randomElement（）方法 O（1） 也是 - ArrayList 所有你需要做的是选择一个随机索引。

I am trying to write an implementation of Set which has an additional method randomElement() which returns an element at random from the Set. I have based the implementation on HashSet for a fast contains() method. I have also used an ArrayList so that the randomElement() method is O(1) too - with an ArrayList all you have to do is choose a random index.

这是我的代码。

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);
            }
        };
    }
}

维护列表以及设置是它使 remove（）方法 O（n），因为首先必须在 ArrayList 中找到元素，然后所有其他元素一个地方。所以我想知道是否可以写出这样一个 Set 其中所有五个操作 size（）， contains（）， add（）， remove（） c $ c> randomElement（）是 O（1）？

The drawback to maintaining a List as well as a Set is that it makes the remove() method O(n) because the element has to be found in the ArrayList first, and then all other elements have to be moved along one place. So I was wondering whether it is possible to write such a Set where all five operations size(), contains(), add(), remove() and randomElement() are O(1)?

推荐答案

我唯一可以想到的是用一个HashMap替换你的集合，从你的元素映射到它在arrayList中的位置。大小，包含，添加和随机都会一样。对于删除，你可以这样做：

The only thing I can think of is to replace your set with a HashMap that maps from your element to it's position in the arrayList. size, contains, add and random will be the same. For remove you would do as follows:

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)

这使得这个工作是什么，你不需要任何特定的顺序数组，你只需要一个随机访问存储，所以改变顺序或数据不会导致任何问题，只要你保持它与你的hashmap同步。

What makes this work is that you don't need any particular order in your array, you just need a random access storage so changing the order or the data will not cause any problems as long as you keep it in sync with your hashmap.

这篇关于用randomElement（）方法编写Set实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！