Класс 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, а также допускает нулевые элементы. Как и HashSet, он обеспечивает постоянное время выполнения основных операций (add, contains и remove) при условии, что хеш-функция должным образом распределяет элементы по ячейкам. Скорость работы, вероятно, будет немного ниже, чем у HashSet, из-за дополнительных затрат на поддержание связанного списка, за исключением одного случая: итерация над LinkedHashSet требует времени, пропорционального размеру множества, независимо от его емкости. Итерация над HashSet будет, вероятно, более дорогой, требуя времени, пропорционального его емкости.

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

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

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

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

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

Этот класс является членом Java Collections Framework.