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


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

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

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

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

7 53

7 ответов:

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

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

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

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

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

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

EDIT: Я вернулся. Действительно, если вам не нужен параллелизм, вам лучше поддерживать очередь и устанавливать ее отдельно. Для того, что я делал, параллелизм был целью, но лучшее решение, которое я мог придумать, учитывая, что ограничение было проблематичным; в основном, поскольку он использовал ConcurrentHashMap, чем больше вы удаляли элемент "head" из очереди (основная вещь, связанная с очередью), тем более несбалансированной хэш-таблица станет со временем. Я все еще можете поделиться этим кодом с вами, но я сомневаюсь, что вы действительно этого хотите.

EDIT: для случая, когда требуется параллелизм я дал этот ответ: Одновременно Установить Очередь

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