Очередь, которые гарантируют уникальность элементов?
Я ищу реализацию java.util. Очередь или что-то в наборе Google, кто ведет себя как Очередь, но также и удостоверяется, что каждый элемент очереди уникален. (вся дальнейшая вставка не будет иметь никакого эффекта),
Это - это возможное, или я должен буду сделать это вручную?
На данный момент я использую Очередь с реализацией LinkedList, и я проверяю уникальность перед вставкой. (Я использую Карту стороны для того, чтобы сделать это, добавляю / удаляют элемент из карты стороны прежде / после queu). Мне не нравится он слишком много.
Любой вход приветствуется. Если это не находится в java.util пакете, то, возможно, это - плохая идея?
5 ответов
Как насчет 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.
Это очень хороший вопрос. Прямого решения не существует. Я откопаю код, который я написал некоторое время назад, который пытался это сделать, и вернусь и отредактирую этот ответ.
РЕДАКТИРОВАТЬ: Я вернулся. На самом деле, если вам не нужен параллелизм, лучше поддерживать Queue и Set отдельно. Для того, что я делал, целью был параллелизм, но лучшее решение, которое я мог придумать с учетом этого ограничения, было проблематичным; в основном, поскольку он использовал ConcurrentHashMap, чем больше вы удаляли «головной» элемент из очереди (основная вещь, связанная с очередью), тем более несбалансированной хеш-таблица со временем становилась. Я все еще могу поделиться с вами этим кодом, но я сомневаюсь, что вы действительно этого хотите.
РЕДАКТИРОВАТЬ: Для случая, когда требуется параллелизм, я дал такой ответ: Очередь одновременного набора
Проверка уникальности, конечно, требует затрат (либо в пространстве, либо во времени). Похоже, было бы интересно работать с чем-то вроде PriorityQueue, который будет поддерживать кучу, отсортированную по Comparator элементов. Возможно, вы сможете использовать это для более эффективной (O (log n)) проверки существования без поддержки дополнительной карты.
Если вы действительно хотите обернуть очередь средством проверки уникальности, я настоятельно рекомендую использовать Google Collections ForwardingQueue для создания такой вещи.