java - Java 中是否有任何无序、可重复的 Collection 类？

This question already has answers here:

Does Java have a multiset data structure like the one in C++ STL?

(7 个回答)


5年前关闭。




我希望一个集合包含无序，可重复的项目。
在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();
}

也就是说，我每次都想随机获得一个项目。我怎样才能实现它？

最佳答案

您可以通过包装 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。但是，还有一个使用 ArrayList 的替代实现，它有点复杂，但提供了一个 randomRemove ，即 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 实现。

关于java - Java 中是否有任何无序、可重复的 Collection 类？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36512569/