Класс 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.