确保元素唯一性的队列？

我正在寻找 java.util 的实现。队列或 Google 集合中的其他元素，它们的行为类似于 Queue，但也确保队列中的每个元素都是唯一的。(所有进一步插入将无效)

It's that possible, or will I have to do it by hand?

现在我使用一个 Queue 和一个 LinkedList 实现，并在插入之前检查惟一性。(我使用 side Map 来完成这项工作，在队列之前/之后从 side Map 中添加/删除元素)。我不太喜欢。

任何输入都是受欢迎的。如果 java.util 包中没有，那么这可能是个坏主意？

56779 次浏览
小开

我倾向于维护一个包含一个键的 HashSet，该键可以与它并排地唯一标识队列中的项。然后只需检查 HashSet，在添加之前查看该项是否在队列中。当您从 Queue 中删除一个项目时，也只需从 HashSet 中删除该键。

小开
最佳答案

LinkedHashSet呢? 它的迭代器保持插入顺序，但是因为它是 Set，所以它的元素是唯一的。

As its documentation says,

Note that insertion order is 没有 affected if an element is 重新插入 into the set.

In order to efficiently remove elements from the head of this "queue", go through its iterator:

Iterator<?> i = queue.iterator();
...
Object next = i.next();
i.remove();
小开

据我所知，这并不存在，但是使用 LinkedList和 Set实现起来相当简单:

/**
* Thread unsafe implementation of UniqueQueue.
*/
public class UniqueQueue<T> implements Queue<T> {
private final Queue<T> queue = new LinkedList<T>();
private final Set<T> set = new HashSet<T>();


public boolean add(T t) {
// Only add element to queue if the set does not contain the specified element.
if (set.add(t)) {
queue.add(t);
}


return true; // Must always return true as per API def.
}


public T remove() throws NoSuchElementException {
T ret = queue.remove();
set.remove(ret);
return ret;
}


// TODO: Implement other Queue methods.
}
小开

Checking uniqueness of course has a cost (either in space or time). Seems like it might be interesting to work from something like a PriorityQueue which will maintain a heap sorted by Comparator of the elements. You might be able to leverage that to more efficiently (O(log n)) check existence without maintaining a side map.

如果您确实想用唯一性检查器包装 Queue，我强烈建议使用 GoogleCollections前进队列来构建这样的东西。

小开

This is a very good question. There is no existing straightforward solution. I'll dig up some code I wrote a while back that attempted to do this, and come back and edit this answer.

EDIT: I'm back. Truly, if you don't need concurrency, you are better off maintaining a Queue and Set separately. For what I was doing, concurrency was a goal, but the best solution I could come up with given that constraint was problematic; basically, since it used a ConcurrentHashMap, the more you were removing the "head" element from the queue (a basic thing to do with a queue), the more unbalanced the hash table would become over time. I can still share this code with you, but I doubt you really want it.

编辑: 对于需要并发的情况，我给出了以下答案: 并发集队列

小开

只是为了完成亚当斯基的回答:

/**
* A queue that keeps each element only once.
* If you try to add an element that already exists - nothing will happen.
*
* @author Adamski http://stackoverflow.com/a/2319156/827927
* @NotThreadSafe
*/
public class UniqueQueue<T> implements Queue<T> {


private final Queue<T> queue = new LinkedList<T>();
private final Set<T> set = new HashSet<T>();


@Override public boolean add(T t) {
// Only add element to queue if the set does not contain the specified element.
if (set.add(t))
queue.add(t);
return true; // Must always return true as per API def.
}


@Override public boolean addAll(Collection<? extends T> arg0) {
boolean ret = false;
for (T t: arg0)
if (set.add(t)) {
queue.add(t);
ret = true;
}
return ret;
}


@Override public T remove() throws NoSuchElementException {
T ret = queue.remove();
set.remove(ret);
return ret;
}


@Override public boolean remove(Object arg0) {
boolean ret = queue.remove(arg0);
set.remove(arg0);
return ret;
}


@Override public boolean removeAll(Collection<?> arg0) {
boolean ret = queue.removeAll(arg0);
set.removeAll(arg0);
return ret;
}


@Override public void clear() {
set.clear();
queue.clear();
}


@Override public boolean contains(Object arg0) {
return set.contains(arg0);
}


@Override public boolean containsAll(Collection<?> arg0) {
return set.containsAll(arg0);
}


@Override public boolean isEmpty() {
return set.isEmpty();
}


@Override public Iterator<T> iterator() {
return queue.iterator();
}


@Override public boolean retainAll(Collection<?> arg0) {
throw new UnsupportedOperationException();
}


@Override public int size() {
return queue.size();
}


@Override public Object[] toArray() {
return queue.toArray();
}


@Override public <T> T[] toArray(T[] arg0) {
return queue.toArray(arg0);
}


@Override public T element() {
return queue.element();
}


@Override public boolean offer(T e) {
return queue.offer(e);
}


@Override public T peek() {
return queue.peek();
}


@Override public T poll() {
return queue.poll();
}
}
小开

不幸的是，它并不存在。由于我需要这样一个队列，我已经开发了一个由一个集支持的阻塞队列，启发了 并发。 LinkedBlockingQueue。

你可以在这里找到:

Https://github.com/bvanalderweireldt/concurrent-unique-queue

例如:

final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1);
queue.offer(new Integer(1)); //True
queue.offer(new Integer(1)); //False

你可以和 Maven 一起使用:

<dependency>
<groupId>com.hybhub</groupId>
<artifactId>concurrent-util</artifactId>
<version>0.1</version>
</dependency>
小开

我回答的有点晚，但是我最终使用 ArrayDeque 解决了一个类似的问题，并覆盖了我需要的 add 方法。

    Deque<Long> myQueue = new ArrayDeque<Long>() {
@Override
public boolean add(Long e) { return !this.contains(e) && super.add(e);}
};
小开

在初始化队列变量时，可以重写 add 方法。

Queue<T> queue = new PriorityQueue<>(){
@Override
public boolean add(T t) {
return !this.contains(t) && super.add(t);
     

};

或者可以实现 Queue 接口。


提交答案