Java中是否存在任何无序,可重复的Collection类？

Question

我想要一个包含无序,可重复项目的集合.在Java中,Set是不可重复的,List是有序的,这不是我想要的.

似乎Pool是一个合适的集合,但它在Java中不存在.界面应如下:

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

它存在于某个地方吗？

---

补充:

我意识到我错误地表达了自己的想法.事实上,我希望有这样的界面:

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

也就是说,我希望每次都能得到一个项目.我怎样才能实现它？

Answer 1

你似乎在描述番石榴Multiset,更具体地说HashMultiset.

Java SE中不存在这样的集合,尽管您可以相当容易地构建自己的集合,具体取决于您想要的功能数量.你基本上有一个HashMap<T, Integer>或类似的东西.

仅举例如:

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

您可以Pool<T>通过包装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()));
    }
}

这不会特别有效，因为remove这是O(N)标准List实现。然而，有一个使用ArrayListthat 的替代实现有点复杂，但提供了一个randomRemovethat O(1)。这个想法是将列表视为动态数组并自己管理“大小”。

像这样的东西：

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

注意：当您尝试删除元素时，这两个版本都不会处理池为空的情况。两者都没有被编译或测试。请相应地对待代码。

最后，如果您尝试使用未排序的集合类型来实现，那么您不太可能能够有效地删除随机元素。提示：对于任何实际的集合数据结构来说，删除集合迭代器返回的第一个迭代器都不是真正随机的。这也适用于（假设的）Bag实现。