Java 确保元素唯一性的队列？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2319086/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
A Queue that ensure uniqueness of the elements?
提问by Antoine Claval
I'm looking for a implementation of java.util.Queue or something in the Google collection who behave like a Queue, but also ensure that each element of the queue is unique. (all further insertion will have no effect)
我正在寻找 java.util.Queue 的实现或谷歌集合中表现得像队列的东西，但也要确保队列的每个元素都是唯一的。（所有进一步插入将无效）
It's that possible, or will I have to do it by hand?
这是可能的，还是我必须手动完成？
For now I'm using a Queue, with a LinkedList implementation, and I check the uniqueness before insertion. ( I use a side Map for doing this, add / remove element from the side map before / after the queu ). I don't like it too much.
现在我正在使用队列和 LinkedList 实现，并在插入前检查唯一性。（我使用侧图来执行此操作，在队列之前/之后从侧图中添加/删除元素）。我不太喜欢它。
Any input is welcome. If it's not in the java.util package, then maybe it's a bad idea?
欢迎任何意见。如果它不在 java.util 包中，那么这可能是个坏主意？
采纳答案by erickson
How about a LinkedHashSet? Its iterator preserves insertion order, but because it's a Set, its elements are unique.
怎么样LinkedHashSet？它的迭代器保留插入顺序，但因为它是 a Set，所以它的元素是唯一的。
As its documentation says,
正如其文档所说，
Note that insertion order is notaffected if an element is re-insertedinto 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();
回答by tvanfosson
I'd be tempted to maintain a HashSetcontaining a key that uniquely identifies the items in the queue side-by-side with it. Then just check the HashSet to see if the item is in the queue before adding it. When you remove an item from the Queue, simply remove the key from the HashSet as well.
我很想维护一个HashSet ，其中包含一个键，该键唯一标识与它并排的队列中的项目。然后只需在添加之前检查 HashSet 以查看该项目是否在队列中。当您从队列中删除一个项目时，也只需从 HashSet 中删除键。
回答by Adamski
This doesn't exist as far as I know but would be fairly simple to implement using a LinkedListin conjunction with a Set:
据我所知，这并不存在，但使用 aLinkedList与 a 结合使用会相当简单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.
}
回答by Alex Miller
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.
检查唯一性当然有成本（空间或时间）。似乎从 PriorityQueue 之类的东西中工作可能会很有趣，它会维护一个按元素的 Comparator 排序的堆。您可能能够利用它来更有效地 (O(log n)) 检查存在，而无需维护侧图。
If you do want to wrap a Queue with a uniqueness checker, I would strongly recommend using the Google Collections ForwardingQueueto build such a thing.
如果您确实想用唯一性检查器包装 Queue，我强烈建议您使用 Google Collections ForwardingQueue来构建这样的东西。
回答by Kevin Bourrillion
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.
编辑：我回来了。确实，如果您不需要并发性，最好分别维护 Queue 和 Set。对于我正在做的事情，并发是一个目标，但鉴于这种约束，我能想出的最佳解决方案是有问题的；基本上，因为它使用了 ConcurrentHashMap，您从队列中移除“头”元素的次数越多（与队列有关的基本操作），哈希表会随着时间的推移变得越不平衡。我仍然可以与您分享此代码，但我怀疑您是否真的想要它。
EDIT:For the case where concurrency is required I gave this answer: Concurrent Set Queue
编辑：对于需要并发的情况，我给出了这个答案： Concurrent Set Queue
回答by Erel Segal-Halevi
Just to complete Adamski's answer:
只是为了完成亚当斯基的回答：
/**
* 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();
}
}
回答by Benoit Vanalderweireldt
Unfortunately it doesn't exist. Since I needed such a Queue I have developed a Blocking Queue backed by a set, inspired by java.util.concurrent.LinkedBlockingQueue.
不幸的是它不存在。由于我需要这样一个队列，我开发了一个由一组支持的阻塞队列，受java.util.concurrent.LinkedBlockingQueue 的启发。
You can find it here :
你可以在这里找到它 ：
https://github.com/bvanalderweireldt/concurrent-unique-queue
https://github.com/bvanalderweireldt/concurrent-unique-queue
Example :
例子 ：
final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1);
queue.offer(new Integer(1)); //True
queue.offer(new Integer(1)); //False
You can use it with Maven :
您可以将它与 Maven 一起使用：
<dependency>
<groupId>com.hybhub</groupId>
<artifactId>concurrent-util</artifactId>
<version>0.1</version>
</dependency>
回答by Tom
I am a bit late to answer but I ended up solving a similar problem using an ArrayDeque and overriding the add method that I needed.
我回答有点晚，但我最终使用 ArrayDeque 解决了类似的问题并覆盖了我需要的 add 方法。
Deque<Long> myQueue = new ArrayDeque<Long>() {
@Override
public boolean add(Long e) { return !this.contains(e) && super.add(e);}
};
