是否有一个队列（PriorityQueue）实现也是一个集合？

Question

我正在寻找 PriorityQueue实现也是一个 Set。

compareTo 实现如果其元素不能有与 equals 实现一致的要求。

java 有没有这样的实现？

更新：我现在使用 SortedSet 作为内部集合来实现它。所以我只需要实现缺少的方法来满足队列接口。我还忘记提及，它也必须是一个有界队列，因此它具有容量，并在达到容量时丢弃集合的最后一个元素。

Answer 1

如果拥有一个具有“类似集合”行为的队列就足够了，而且您只是不想接受重复的条目，那么我认为，一个简单的解决方案可能是子类化 PriorityQueue 并覆盖add()、addAll() 和 offer() 方法，例如：

@Override
public boolean offer(E e) {
  if (contains(e)) {
    return false; 
  } else {
    return super.offer(e);
  }
}

顺便说一句 - add() 调用 offer() 内部，所以也许只需重写 offer() 方法并在那里进行检查就足够了。

Answer 2

TreeSet 是一个提供有序迭代器的集合。它实现了 SortedSet 接口，它保证由 iterator 方法返回的迭代器将按照其自然顺序（通过 Comparable）确定的升序返回集合的元素，或由创建集合时赋予该集合的比较器确定。

Answer 3

那么 PriorityQueue 本身将依赖于 Comparitor 或项目的自然顺序进行排序，同样，Set 也将依赖于基于自然排序或 Comparitor 函数，所以不，我不认为它作为默认 Java 安装的一部分存在......

但是如果速度不成问题，您可能可以很容易地创建一个简单地实现您想要的接口，并使用它们的自然支持等...又名

MyQueueSet extends PriorityQueue implements Set {
    HashSet set;
    ...
}

不幸的是，Java 的 java.util.* 数据集类并不总是最容易扩展的，而不需要重写其代码块。

PriorityQueue 支持是堆排序的元素列表，因此插入新元素然后执行 contains(e) 测试将执行 O(n) 搜索，因为排序是基于在队列上，不是在数据值上，如果您包含 HashSet 来支持 Set 功能，则可以缩短查找时间大量的代价是维护数据集引用两次（请记住，Java 是按值传递的，所有对象都位于堆上）。这应该可以提高大型集合的性能。

Answer 4

PriorityQueue 是一个 AbstractCollection - 它具有与 Set 几乎相同的接口。我确信制作一个将 PriorityQueue 转换为 Set 的包装器会很容易。如果您确实需要强制执行，您可以保留插入元素的侧面哈希表以避免重复。

我不认为 PriorityQueue 要求 CompareTo 与 equals 一致。 PriorityQueue 根本不使用 equals（除了它继承的 AbstractCollection 操作？）。