За счет чего LinkedHashSet сохраняет порядок элементов?

LinkedHashSet является наследником HashSet и реализует интерфейс Set. Его ключевая особенность — предсказуемый порядок итерации, который соответствует порядку добавления элементов (insertion-order). Это достигается за счет изменения внутренней структуры данных.

Внутренняя реализация

LinkedHashSet внутри использует LinkedHashMap в качестве backing map. В то время как обычный HashSet хранит элементы в массиве бакетов (корзин) на основе хэш-кода, LinkedHashMap расширяет эту структуру, добавляя к каждой записи (Entry) два дополнительных поля: before и after. Эти поля образуют двусвязный список, соединяющий все записи в порядке их добавления.

Как работает добавление элемента

• При вызове метода add() элемент (объект) помещается в хэш-таблицу, как и в HashSet, для быстрого поиска по хэш-коду.
• Одновременно с этим, запись (узел) добавляется в конец внутреннего двусвязного списка.
• Если элемент уже существует (дубликат), порядок списка не меняется, так как Set не допускает дубликатов.

Пример кода и итерации

import java.util.LinkedHashSet;

public class Example {
    public static void main(String[] args) {
        LinkedHashSet set = new LinkedHashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple"); // Дубликат, не добавится
        
        // Итерация выведет элементы в порядке добавления
        for (String fruit : set) {
            System.out.println(fruit); // Apple, Banana, Cherry
        }
    }
}

Где применяется

LinkedHashSet полезен в сценариях, где важен порядок, но при этом необходима уникальность элементов и быстрый доступ по значению (в среднем O(1)). Например: кэширование с LRU-политикой (хотя для LRU обычно используют LinkedHashMap напрямую), удаление дубликатов из списка с сохранением исходного порядка, или реализация очереди уникальных элементов.

Вывод: Используйте LinkedHashSet, когда вам нужна коллекция без дубликатов, но при этом критично сохранить порядок вставки элементов, и вы готовы к небольшому дополнительному расходу памяти на поддержку связного списка.