一个提供不重复元素的Java队列实现

Question

我正在寻找一个java.util.Queue的实现方式，它最多只能排队相同元素一次。

例如，这样的specialQueue应该表现如下：

E e1;
E e2;
E e3;
//...
assertThat( e1, is(e2) );
assertThat( e1, is(not(e3)) );

Queue<E> specialQueue;
//...
specialQueue.offer(e1);
specialQueue.offer(e2);
specialQueue.offer(e3);


assertThat( specialQueue.poll(), is(e1) );
assertThat( specialQueue.poll(), is(e3) );
assertThat( specialQueue.poll(), is(null) );
// FIFO semantics are not relevant to the question

specialQueue.offer(e3)
assertThat( specialQueue.poll(), is(null) );

我想出了一个管理内部 Set<E> alreadySeenElements 的实现，并通过检查该集合以防止将元素添加到委派队列中。 我想知道是否已经存在经过“实战测试”的实现。

- Abdull

---

看这里：https://dev59.com/OXE95IYBdhLWcg3watQ3。 - Sneh

@Sneh，感谢您让我注意到另一个问题，它确实非常接近我的问题。那里的答案似乎更关注元素在队列中输入时的唯一性，而不是队列生命周期内元素的唯一性。 - Abdull

我认为唯一性要求违反了队列协议。例如，Queue.add必须在容量限制导致无法添加元素时返回true或抛出IllegalStateException异常。 - Evgeniy Dorofeev

@EvgeniyDorofeev，说得好。但是唯一性约束是否违反了容量约束？此外，Java类库包括Queue子类，例如java.util.ArrayDeque，它明确地删除了容量限制。 - Abdull

是的，我认为这是一种违规行为。当然，你想要的东西是完全合法的，但不要称其为队列，也不要实现队列。这就是我的观点。 - Evgeniy Dorofeev

如果“FIFO语义不相关”，那么它怎么能被称为队列呢？ - Raja Anbazhagan

Answer 1

像评论者建议的那样，您更多地描述了一种特殊类型的Set而不是Queue。从我理解的来看，您的要求是：

• 插入顺序迭代
• 集合中的每个元素都是唯一的（非相等）
• 先前看到的元素永远不能被重新添加

前两个要求可以通过LinkedHashSet很好地满足，就像this question所建议的那样。最后一个要求则更为奇怪，并需要一些内部存储先前看到的值的机制。类似于：

public class SeenOnceLinkedHashSet<E> implements Set<E> {
  private LinkedHashSet<E> data;
  private HashSet<E> seen;

  public boolean add(E e) {
    boolean newValue = seen.add(e);
    if (newValue) {
      return data.add(e);
    }

  // and so on in other methods
}

请注意，这个类具有无限的内部存储空间。如果您以其他Set处理方式使用此类，很容易导致内存不足问题。如果您需要某种“已添加”的概念，则无法避免这种情况。您可以使用更优雅的东西，比如BloomFilter，但这会引入误报。

就我个人而言，我建议您重新审视您的要求。任何形式的无限空间数据结构几乎肯定是代码异味。例如，您是否可以使用一个包装器类，提供更有用的.equals()定义？或者在对象构造时添加额外的安全检查，以便首先不会构造出错误的对象？

- dimo414