Set vs List when need both unique elements and access by index

Question

I need to keep a unique list of elements seen and I also need to pick random one from them from time to time. There are two simple ways for me to do this.

1. Keep elements seen in a Set - that gives me uniqueness of elements. When there is a need to pick random one, do the following:

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

2. Keep elements seen in a List - this way no need to convert to array as there is the get() function for when I need to ask for a random one. But here I would need to do this when adding.

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

So my question is which way would be more efficient? Is converting to array more consuming or is indexOf worse? What if attempting to add an element is done 10 or 100 or 1000 times more often?

I am interested in how to combine functionality of a list (access by index) with that of a set (unique adding) in the most performance effective way.

Answer 1

If using more memory is not a problem then you can get the best of both by using both list and set inside a wrapper:

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 ...
}