需要两个唯一元素和索引访问时设置vs列表

Question

我需要保留一个独特的元素列表,我还需要随时从中随机选择一个元素.我有两种简单的方法可以做到这一点.

1. 保持在集合中看到的元素 - 这给了我元素的独特性.如果需要随机选择一个,请执行以下操作:

   elementsSeen.toArray()[random.nextInt(elementsSeen.size())]
   

2. 保持List中的元素 - 这种方式不需要转换为数组,因为当我需要随机的时候有get()函数.但是在这里我需要在添加时执行此操作.

   if (elementsSeen.indexOf(element)==-1) {elementsSeen.add(element);}
   

所以我的问题是哪种方式会更有效率？转换为数组更多消耗还是indexOf更糟？如果尝试添加元素的次数是10次或100次或1000次,会怎么样？

我感兴趣的是如何以最有效的方式将列表的功能(按索引访问)与集合的功能(唯一添加)相结合.

Answer 1

如果使用更多内存不是问题,那么你可以通过在包装器中使用list和set来充分利用它们:

public class MyContainer<T> {
    private final Set<T> set = new HashSet<>();
    private final List<T> list = new ArrayList<>();

    public void add(T e) {
        if (set.add(e)) {
            list.add(e);
        }
    }

    public T getRandomElement() {
        return list.get(ThreadLocalRandom.current().nextInt(list.size()));
    }
    // other methods as needed ...
}

Answer 2

HashSet和TreeSet都扩展AbstractCollection,包括toArray()如下所示的实现:

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

如您所见,它负责为数组分配空间,以及创建Iterator复制对象.因此,对于a Set,添加是O(1),但由于元素复制操作,检索随机元素将是O(N).

一List,在另一方面,可以让你快速访问支持数组中的特定指数,但不保证唯一性.你将不得不重新实现add,remove和相关方法,以保证在插入唯一性.添加唯一元素将是O(N),但检索将是O(1).

因此,它实际上取决于您的潜在高使用点的哪个区域.是否会大量使用添加/删除方法,并且谨慎使用随机访问？或者这将是一个最重要的检索容器,因为在程序的生命周期中将添加或删除很少的元素？

如果是前者,我建议使用Setwith toArray().如果是后者,那么实现一个唯一的List以利用快速检索可能是有益的.重要的缺点是add包含许多边缘情况,标准Java库需要非常谨慎地以高效的方式工作.您的实施是否符合相同的标准？