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