Очередь, обеспечивающая уникальность элементов?

Question

Я ищу реализацию java.util.Queue или что-то в коллекции Google, которая ведет себя как очередь, но также гарантирует, что каждый элемент очереди уникален. (все дальнейшие вставки не будут иметь никакого эффекта)

Это возможно, или мне придется делать это вручную?

На данный момент я использую очередь с реализацией LinkedList и проверяю уникальность перед вставкой. (Для этого я использую карту стороны, добавляю / удаляю элемент из карты стороны до / после очереди). Мне это не очень нравится.

Любые входные данные приветствуются. Если его нет в пакете java.util, то может быть, это плохая идея?

Answer 1

Как насчет LinkedHashSet? Его итератор сохраняет порядок вставки, но, поскольку это Set, его элементы уникальны.

Как сказано в документации,

Обратите внимание, что порядок вставки не влияет, если элемент повторно вставлен в набор.

Чтобы эффективно удалить элементы из заголовка этой «очереди», пройдите через ее итератор:

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

Answer 2

Насколько я знаю, этого не существует, но его было бы довольно просто реализовать, используя 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.
}

Answer 3

Просто чтобы завершить ответ Адамски:

/**
 * 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();
}
}

Answer 4

Проверка уникальности, конечно, имеет свою стоимость (в пространстве или времени). Похоже, может быть интересно работать с чем-то вроде PriorityQueue, которое будет поддерживать кучу, отсортированную по Comparator элементов. Возможно, вам удастся использовать это для более эффективной (O (log n)) проверки существования без ведения карты сторон.

Если вы хотите обернуть очередь проверкой уникальности, я настоятельно рекомендую использовать Google Collections ForwardingQueue для создания такой вещи.

Answer 5

Я бы хотел сохранить HashSet , содержащий ключ, который однозначно идентифицирует элементы в очереди рядом с ним. Затем просто проверьте HashSet, чтобы увидеть, находится ли элемент в очереди, прежде чем добавить его. Когда вы удаляете элемент из очереди, просто удалите также ключ из HashSet.

Answer 6

К сожалению, его не существует. Поскольку мне нужна была такая очередь, я разработал очередь блокировки, основанную на наборе, вдохновленном java.util.concurrent.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>

Answer 7

Это очень хороший вопрос. Существует не существует простого решения. Я найду некоторый код, который я недавно написал, чтобы попытаться это сделать, и вернусь и отредактирую этот ответ.

РЕДАКТИРОВАТЬ: Я вернулся. Действительно, если вам не нужен параллелизм, вам лучше поддерживать очередь и набор отдельно. Для того, что я делал, параллелизм был целью, но лучшее решение, которое я мог придумать, учитывая, что ограничение было проблематичным; в основном, поскольку он использовал ConcurrentHashMap, чем больше вы удаляете элемент «head» из очереди (основное, что нужно сделать с очередью), тем более несбалансированной будет хеш-таблица со временем. Я все еще могу поделиться этим кодом с вами, но я сомневаюсь, что вы действительно этого хотите.

РЕДАКТИРОВАТЬ: Для случая, когда требуется параллелизм, я дал такой ответ: Очередь одновременных наборов

Answer 8

Я немного опоздал с ответом, но в итоге решил аналогичную проблему, используя ArrayDeque и переопределив нужный мне метод add.

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