Java中是否有无序、可重复的集合类？

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

也就是说，我想要每次随机获取一个项目。我该如何实现？

- jinge

---

尝试使用Guava库。 - piyush121

那个接口真的很简陋。set和get应该是什么意思？set是“放入一个T”，而get是“移除并返回一个T”吗？如果是这样，大多数有序集合都可以使用add和某种形式的remove或pop来支持它们。 - user2357112

你有特别的原因在寻找一个明确无序的集合吗？有序似乎并不是什么障碍。 - Dolda2000

Guava的HashMultiset就是你要找的。 - fps

Answer 1

你似乎在描述Guava 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);
    }
}

- Radiodef

---

它可能需要实现Iterable<T>甚至是Collection<T>。而且现在我们有了Java 8，你可以大大简化代码。 - Boris the Spider

@BoristheSpider Java 8能在整洁方面提供哪些帮助？ - jinge

@jinge 一个 Map.computeIfAbsent 和 Map.merge 的组合可以让大部分代码变成一行。此外，Counter 是不必要的。 - Boris the Spider

避免装箱问题，通过创建额外的对象来解决 - 不确定这是否真正有所帮助。 - Boris the Spider

@jinge 在我更新后的例子中，Java 8 中的“add”方法只需要一行代码就可以实现：map.merge(obj, 1, count -> count + 1);。如果我们完全实现了“Collection”，那么还会有更多类似的东西。 - Radiodef

Answer 2

你可以通过包装一个 List<T> 来实现你的 Pool<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()));
    }
}

这并不是特别高效的，因为在标准的List实现中，remove的时间复杂度为O(N)。然而，有一种使用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实现也是如此。

- Stephen C

---

在FasterPool代码片段中，如果我们将随机位置的元素与最后一个元素交换，然后删除最后一个元素，那么我们是否可以不管理自己的size？ - Jae Heon Lee

很棒的答案。但我突然想到一个问题，当你与其中一些物品交换位置时，每个物品是否总是具有相同的概率？ - jinge

@JaeHeonLee - 是的。那样可以。 - Stephen C

@jinge - 是的。在每个阶段，您都使用具有均匀分布的PRNG从“数组”中选择一个元素。事实上，元素在数组中的不同位置并不影响这一点。 - Stephen C

Answer 3

如果需要随机排序，一种方法是收集并洗牌。

List<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
Collections.shuffle(list);

System.out.println(list);

输出：

[B, A, C]

- muzahidbechara