Класс LinkedHashSet<E>

Реализация интерфейса Set на основе хеш-таблицы и связного списка с определённым порядком обхода. Эта реализация отличается от HashSet тем, что поддерживает двусвязный список, проходящий через все элементы. Этот связный список определяет порядок обхода (порядок итерации), то есть порядок, в котором элементы были добавлены в множество (порядок вставки). Элемент, добавленный раньше всех (самый старый), находится первым, а добавленный позже всех (самый новый) — последним. Обратите внимание, что порядок обхода не меняется, если элемент повторно добавляется в множество с помощью метода add. (Элемент e повторно добавляется в множество s, если s.add(e) вызывается в момент, когда s.contains(e) непосредственно перед вызовом возвращает true.) Представление этого множества с обратным порядком имеет противоположный порядок: первым в нём будет самый новый элемент, а последним — самый старый. Порядок обхода элементов, уже находящихся в множестве, можно изменить с помощью методов addFirst и addLast.

Эта реализация избавляет клиентский код от неопределённого, обычно хаотичного порядка, предоставляемого HashSet, не неся при этом повышенных издержек, связанных с TreeSet. Её можно использовать для создания копии множества с тем же порядком элементов, что и в исходном множестве, независимо от реализации исходного множества:

    void foo(Set<String> s) {
        Set<String> copy = new LinkedHashSet<>(s);
        ...
    }

Этот класс предоставляет все необязательные операции интерфейсов Set и SequencedSet и допускает наличие элементов null. Как и HashSet, он обеспечивает постоянное время выполнения основных операций (add, contains и remove), если хеш-функция надлежащим образом распределяет элементы по корзинам. Производительность, вероятно, будет лишь немного ниже, чем у HashSet, из-за дополнительных затрат на поддержку связного списка; есть одно исключение: итерация по LinkedHashSet требует времени, пропорционального размеру множества, независимо от его ёмкости. Итерация по HashSet, вероятно, будет дороже и потребует времени, пропорционального его ёмкости.

Производительность связного хеш-множества зависит от двух параметров: начальной ёмкости и коэффициента загрузки. Они определены так же, как для HashSet. Однако обратите внимание, что выбор чрезмерно большого значения начальной ёмкости менее негативно сказывается на этом классе, чем на HashSet, поскольку ёмкость не влияет на время итерации для этого класса.

Обратите внимание, что эта реализация не синхронизирована. Если несколько потоков одновременно обращаются к связному хеш-множеству и хотя бы один из них изменяет множество, доступ необходимо синхронизировать извне. Обычно для этого синхронизацию выполняют по объекту, который естественным образом инкапсулирует множество. Если такого объекта нет, множество следует «обернуть» с помощью метода Collections.synchronizedSet. Лучше всего сделать это при создании множества, чтобы предотвратить случайный несинхронизированный доступ к нему:

  Set s = Collections.synchronizedSet(new LinkedHashSet(...));

Итераторы, возвращаемые методом iterator этого класса, являются быстроотказывающими: если после создания итератора множество каким-либо образом изменяется, кроме как с помощью собственного метода remove итератора, итератор выбрасывает исключение ConcurrentModificationException. Таким образом, при параллельном изменении итератор быстро и корректно завершает работу, вместо того чтобы допускать произвольное недетерминированное поведение в неопределённый момент в будущем.

Обратите внимание, что гарантировать быстроотказывающее поведение итератора нельзя, поскольку, вообще говоря, невозможно дать какие-либо строгие гарантии при несинхронизированном параллельном изменении. Быстроотказывающие итераторы выбрасывают ConcurrentModificationException по возможности. Поэтому было бы неправильно писать программу, корректность которой зависит от этого исключения: быстроотказывающее поведение итераторов следует использовать только для обнаружения ошибок.

Этот класс входит в состав Java Collections Framework.