java - 在需要唯一元素和按索引访问时设置 vs 列表

Question

我需要保留一个唯一的元素列表，并且我还需要不时从它们中随机选择一个。我有两种简单的方法可以做到这一点。

1. 将元素保留在 Set 中 - 这让我拥有了元素的独特性。当需要随机选择一个时，请执行以下操作:

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

2. 保留在列表中看到的元素 - 这样不需要转换为数组，因为当我需要随机请求时有 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 ...
}