Класс Java LinkedHashSet | W3Docs Learn Java

LinkedHashSet<E> — это HashSet<E> с одним дополнительным гарантом: при итерации элементы возвращаются в порядке их первоначальной вставки. Механизм хэш-таблицы идентичен — те же корзины, тот же коэффициент загрузки, те же операции add, remove, contains за практически константное время — но каждая запись содержит два дополнительных указателя (before, after), связывающих записи в двусвязный список по мере их добавления. Итерация обходит именно этот список, а не массив корзин.

Если вам нужна производительность хэш-множества и детерминированный, предсказуемый порядок итерации, LinkedHashSet — это ответ. Для случаев, когда произвольный порядок HashSet создавал проблемы, это практически бесплатное улучшение.

Правило «первая вставка определяет позицию»

Порядок фиксируется в момент первой вставки элемента. Повторное добавление существующего элемента не меняет его позицию:

Set<String> s = new LinkedHashSet<>();
s.add("a");
s.add("b");
s.add("c");
s.add("a");   // already present — returns false, order unchanged
System.out.println(s);   // [a, b, c]

Это делает LinkedHashSet подходящим инструментом для задач «запомнить порядок поступления тегов» или «записывать уникальные события в хронологическом порядке». Если удалить элемент и добавить его снова, он перемещается в конец списка — позиция была привязана к текущей вставке, а новая становится единственной оставшейся.

Цена: дополнительные указатели

Дополнительный механизм упорядочивания имеет свою цену. Каждая запись хранит не только (hash, key, next-in-bucket), как в HashSet, но (hash, key, next-in-bucket, before, after). Это два дополнительных ссылки на элемент — примерно 16 байт на 64-битной JVM. Для множества из 10 миллионов значений Long это около 160 МБ дополнительной памяти. Для большинства прикладного кода это незначительно; для структур данных кэш-размера это уже важно.

Взамен вы получаете O(1) для каждой операции (как у HashSet) плюс стабильный порядок итерации, не зависящий от коэффициента загрузки, рехэширования, распределения хэшей или версии JVM.

Стоимость итерации пропорциональна размеру, а не ёмкости

У LinkedHashSet есть тонкое преимущество перед HashSet: обход LinkedHashSet следует по связному списку, поэтому он посещает ровно size записей. Итерация по HashSet обходит каждую корзину, то есть посещает примерно capacity слотов — включая пустые. Для разреженного множества это может быть существенной разницей. Если вы создаёте множество, расширяете его далеко за пределы элементов, которые планируете хранить, и затем часто итерируете его, LinkedHashSet может итерировать быстрее.

Когда его выбирать

Схема принятия решения:

Порядок не важен, нужна только быстрая проверка наличия → HashSet. Меньше и проще.
Нужно запомнить порядок вставки → LinkedHashSet. Та же скорость для add/contains, предсказуемая итерация.
Нужен сортированный порядок → TreeSet. Другой алгоритм, логарифмические операции.

Наиболее распространённая причина выбрать LinkedHashSet — защитный подход: вы создаёте публичный API, возвращающий Set, и не хотите, чтобы вызывающие зависели от произвольного порядка HashSet. LinkedHashSet — самое разумное, что можно вернуть: он имеет тот же контракт, что и Set, но итерация воспроизводима в разных запусках и JVM, что делает пользовательский вывод стабильным, а тесты — проще в написании.

Практический пример: уникальные теги в порядке появления

Программа ниже строит два множества из одного потока входных тегов: одно с HashSet, другое с LinkedHashSet. Порядок итерации HashSet зависит от JVM (он стабилен, но произволен для конкретной JVM); порядок LinkedHashSet — это в точности порядок первого появления уникальных элементов. Затем показывается правило «удалить и добавить снова», а в конце строится дедупликатор с сохранением порядка длиной в две строки.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class LinkedHashSetShowcase {
  public static void main(String[] args) {
    String[] events = { "login", "view", "purchase", "view", "logout", "login", "view" };

Set<String> hashed = new HashSet<>();
    Set<String> linked = new LinkedHashSet<>();
    for (String e : events) { hashed.add(e); linked.add(e); }

System.out.println("input:    " + Arrays.toString(events));
    System.out.println("HashSet:        " + hashed + "   (order may be anything)");
    System.out.println("LinkedHashSet:  " + linked + "   (first-insertion order)");

// --- The 'first-insertion wins' rule ---
    Set<String> demo = new LinkedHashSet<>();
    demo.add("a"); demo.add("b"); demo.add("c");
    demo.add("a");                 // already there — order unchanged
    System.out.println("\nre-add 'a':       " + demo);
    demo.remove("a"); demo.add("a"); // gone then back — moves to end
    System.out.println("remove+re-add 'a': " + demo);

// --- Order-preserving deduplicator in two lines ---
    List<Integer> noisy = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
    List<Integer> deduped = noisy.stream()
        .collect(Collectors.toCollection(LinkedHashSet::new))
        .stream().toList();
    System.out.println("\nnoisy:    " + noisy);
    System.out.println("deduped:  " + deduped + "   (order preserved)");

// --- Iteration cost: LinkedHashSet visits size entries, not capacity slots ---
    Set<Integer> big = new LinkedHashSet<>(2_000_000); // huge capacity, few elements
    for (int i = 0; i < 10; i++) big.add(i);
    long t0 = System.nanoTime();
    int sum = 0;
    for (int x : big) sum += x;
    long t1 = System.nanoTime();
    System.out.println("\nsum of " + big.size() + " elements in a " + 2_000_000
        + "-bucket set: " + sum + "  in " + (t1 - t0) + " ns");
  }
}

Что следует извлечь из запуска:

LinkedHashSet вывел уникальные события в порядке их первого появления. HashSet вывел их в совершенно ином порядке — диктуемом расположением корзин.
Повторное добавление "a" никак не изменило порядок. Удаление и повторное добавление переместило его в конец. Именно первая вставка определяет позицию.
Дедупликатор с сохранением порядка — это однострочник, как только вы знаете приём: собрать в LinkedHashSet, затем обратно в список.
Обход 10 элементов в LinkedHashSet с 2 000 000 корзинами прошёл ровно 10 записей; HashSet той же формы обошёл бы каждую пустую корзину между ними.

Что дальше

Третья стандартная реализация Set даёт вам то, чего не могут ни HashSet, ни LinkedHashSet: сортированную итерацию и возможность задавать диапазонные запросы вида «все теги между a и m». Далее рассмотрим TreeSet.

Практика

Что даёт `LinkedHashSet` по сравнению с обычным `HashSet`?

Итерацию в порядке первой вставки элементов, ценой двух дополнительных ссылок на каждую записьСортированную итерацию по естественному порядку элементовПотокобезопасные операции с использованием внутренних блокировокПоиск за O(log n) вместо O(1), со стабильным порядком как побочным эффектом