Are there any unordered, repeatable Collection classes in Java? [duplicate]

Question

I want a collection contains unordered, repeatable items. In Java, Set is unrepeatable, List is ordered, which are not what I want.

It seems Pool is an appropriate collection, but it doesn't exist in Java. The interface should be as following:

public interface Pool<T> {
    void set(T item);
    T get();
}

Does it exist somewhere?

---

Complementing：

I realize that I expressed my thought incorrectly. Infact, I want to have an interface like this:

public interface Pool<T> {
    void put(T item);
    T randomRemove();
}

That is to say, I want to get an item ramdomly everytime. How can I achieve it?

Answer 1

You seem to be describing the Guava Multiset, and more specifically HashMultiset.

No such collection exists in Java SE, although you could build your own fairly easily, depending on the amount of functionality you want. You'd basically have a HashMap<T, Integer> or something like that.

Just for example:

class MultiSet<T> {
    Map<T, Integer> map = new HashMap<>();

    void add(T obj) {
        Integer count = map.get(obj);
        if (count == null) {
            map.put(obj, 1);
        } else {
            map.put(obj, count + 1);
        }
    }

    void remove(T obj) {
        Integer count = map.get(obj);
        if (count != null) {
            if (count > 1) {
                map.put(obj, count - 1);
            } else {
                map.remove(obj);
            }
        }
    }

    boolean contains(Object obj) {
        return map.containsKey(obj);
    }
}

Answer 2

You can implement your Pool<T> functionality by wrapping a List<T>.

public class ListPool<T> implements Pool<T> {
    private List<T> list = ArrayList<>();

    public void put(T t) {
        list.append(t);
    }

    public T randomRemove() {
        return list.remove(rand.nextInt(list.size()));
    }
}

That won't be particularly efficient because remove is O(N) on the standard List implementations. However, there is an alternative implementation using ArrayList that is a bit more complicated, but provides a randomRemove that is O(1). The idea is to treat the list as a dynamic array and manage the "size" yourself.

Something like this:

public class FasterPool<T> implements Pool<T> {
    private List<T> list = new ArrayList<>();
    private int size = 0;
    Random rand = new Random();

    public void put(T t) {
        if (size == list.size()) {
            list.append(t);
        } else {
            list.set(size, t);
        size++;
    }

    public T randomRemove() {
        int pos = rand.nextInt(size);
        T result = list.get(pos);
        if (pos < size - 1) {
            list.set(pos, list.get(size - 1));
        }
        list.set(size - 1, null);  // avoid memory leak ...
        size--;
        return result;
    }
}

NB: neither version handles the case where the pool is empty when you try to remove an element. Neither has been compiled or tested. Please treat the code accordingly.

Finally, if you try to implement using a collection type that is not ordered, then you are unlikely to be able to remove a random element efficiently. Hint: removing the first one returned by a collection's iterator will not be truly random for any practical collection data structure. This would also apply to a (hypothetical) Bag implementation.