确保元素唯一性的队列？
我正在寻找java.util.Queue或Google集合中类似Queue的东西的实现，但也要确保队列中的每个元素都是唯一的。 （所有进一步插入将不起作用）
这是可能的，还是我必须手工做？
现在我正在使用一个队列，一个LinkedList实现，并且在插入之前检查唯一性。 （我使用一个侧面的Map做这个，在排队之前/之后添加/删除侧面的元素）。 我不喜欢它太多。
任何input是受欢迎的。 如果它不在java.util包中，那么这可能是一个坏主意？
怎么样LinkedHashSet ？ 它的迭代器保留了插入顺序，但是因为它是一个Set ，所以它的元素是唯一的。
正如其文件所述，
请注意，如果将元素重新插入到集合中，则插入顺序不受影响。
为了从这个“队列”的头部有效地移除元素，请遍历它的迭代器：
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. }
我试图维护一个HashSet，其中包含一个唯一标识队列中的项的键。 然后只需在添加HashSet之前查看该项是否在队列中。 从队列中删除项目时，只需从HashSet中删除项目。
检查课程的唯一性会带来成本（无论是在空间还是在时间上）。 看起来好像从PriorityQueue这样的东西开始工作可能会很有趣，它将保持一个由元素比较器sorting的堆。 您可能能够更有效地利用它（O（log n））检查是否存在，而无需维护侧面图。
如果你想用一个唯一性检查器打包队列，我强烈build议使用Google集合转发队列来构build这样的事情。
只是为了完成Adamski的回答：
/** * 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(); } }
这个问题问得好。 没有现有的简单解决scheme。 我将挖掘一些我之前写过的代码，试图做到这一点，然后回来编辑这个答案。
编辑：我回来了。 确实，如果你不需要并发，你最好分开维护一个队列和设置。 对于我在做的事情，并发是一个目标，但是由于这个约束是有问题的，所以我可以提出最好的解决scheme。 基本上，因为它使用的是ConcurrentHashMap，所以从队列中移除“head”元素（对于队列来说是一个基本的事情）越多，散列表就越不平衡。 我仍然可以与你分享这个代码，但我怀疑你真的想要它。
编辑：对于需要并发的情况下，我给了这个答案： 并发集队列
不幸的是，它不存在。 因为我需要这样一个队列，所以我开发了一个由java.util.concurrent.LinkedBlockingQueue启发的集合支持的Blocking Queue。
你可以在这里find它 ：
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>
TreeSet中。 这是一个有序的Set，Set意味着“没有重复的元素”。
