В чём разница между HashSet, LinkedHashSet и TreeSet

Интерфейс Set представляет собой коллекцию уникальных элементов (дубликаты запрещены). В стандартной библиотеке Java есть три основные реализации Set, отличающиеся упорядоченнос...

🟢 Junior Level

Интерфейс Set представляет собой коллекцию уникальных элементов (дубликаты запрещены). В стандартной библиотеке Java есть три основные реализации Set, отличающиеся упорядоченностью, скоростью работы и внутренним устройством:

Характеристика	`HashSet`	`LinkedHashSet`	`TreeSet`
Порядок элементов	Не гарантирован (хаотичный, зависит от хэша)	Порядок вставки (Insertion-Order)	Отсортированный (Natural или Comparator)
Базовая структура	Хэш-таблица (`HashMap`)	Хэш-таблица + двусвязный список	Красно-черное дерево (`TreeMap`)
Сложность `add`/`contains`	$O(1)$ в среднем	$O(1)$ в среднем	$O(\log N)$
Поддержка `null`	✅ Разрешен (один `null`)	✅ Разрешен (один `null`)	❌ Запрещен (`NullPointerException`)
Назначение	Максимальная скорость проверки уникальности	Уникальность + предсказуемый порядок обхода	Уникальность + поиск диапазонов и сортировка

// 1. HashSet: порядок непредсказуем
Set<String> hashSet = new HashSet<>();
hashSet.add("C"); hashSet.add("A"); hashSet.add("B");
// Вывод может быть: [A, B, C] или [C, A, B] в зависимости от JVM

// 2. LinkedHashSet: строго в порядке добавления
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("C"); linkedHashSet.add("A"); linkedHashSet.add("B");
// Вывод ВСЕГДА: [C, A, B]

// 3. TreeSet: автоматически отсортирован
Set<String> treeSet = new TreeSet<>();
treeSet.add("C"); treeSet.add("A"); treeSet.add("B");
// Вывод ВСЕГДА по алфавиту: [A, B, C]

🟡 Middle Level

1. Архитектурное устройство под капотом

Все три реализации множеств являются «обертками» над соответствующими реализациями интерфейса Map:

HashSet<E>        ──► инкапсулирует ──► HashMap<E, Object>
LinkedHashSet<E>  ──► инкапсулирует ──► LinkedHashMap<E, Object>
TreeSet<E>        ──► инкапсулирует ──► TreeMap<E, Object>

Элементы множества помещаются в качестве ключей мапы, а в качестве значения подставляется единый статический фиктивный объект-заглушка: private static final Object PRESENT = new Object();

2. Парадокс производительности итерации: `HashSet` против `LinkedHashSet`

Хотя операции add() и contains() в HashSet и LinkedHashSet выполняются за $O(1)$, операция полного перебора коллекции (итерация) работает принципиально иначе:

Итерация в HashSet имеет сложность $O(\text{capacity} + \text{size})$: Итератор обязан обойти абсолютно все корзины (бакеты) массива таблицы, включая пустые ячейки. Антипаттерн: Если создать new HashSet<>(1_000_000) и положить всего 10 элементов, итератор будет проверять 1 000 000 ячеек, тратя десятки миллисекунд впустую!
Итерация в LinkedHashSet имеет сложность строго $O(\text{size})$: Каждая нода LinkedHashMap$Entry имеет указатели before и after. Итератор обходит элементы напрямую по связному списку от первого к последнему, не обращая внимания на пустые корзины хэш-таблицы.

3. Навигационные возможности `TreeSet`

TreeSet реализует интерфейс NavigableSet, предоставляя богатый инструментарий поиска ближайших значений:

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));

numbers.lower(30);   // 20 (строго меньше < 30)
numbers.floor(30);   // 30 (меньше или равно <= 30)
numbers.ceiling(35); // 40 (больше или равно >= 35)
numbers.higher(40);  // 50 (строго больше > 40)

// Получение среза диапазона:
NavigableSet<Integer> sub = numbers.subSet(20, true, 40, true); // [20, 30, 40]

🔴 Senior Level

1. Трагедия мутабельных объектов в `HashSet` / `LinkedHashSet`

Если поместить в хэш-множество объект, чьи поля участвуют в расчете hashCode(), а затем изменить эти поля — объект станет «призраком»:

class User {
    private String name;
    public User(String name) { this.name = name; }
    public void setName(String name) { this.name = name; }
    @Override public int hashCode() { return Objects.hash(name); }
    @Override public boolean equals(Object o) { ... }
}

Set<User> set = new HashSet<>();
User u = new User("Alice");
set.add(u);

// Модифицируем объект после добавления:
u.setName("Bob"); // Хэш-код изменился!

// КАТАСТРОФА:
System.out.println(set.contains(u)); // false!
System.out.println(set.remove(u));   // false!
System.out.println(set.size());     // 1!

Что произошло под капотом:

При добавлении объект попал в корзину с индексом hash("Alice") & mask.
После мутации вызов contains(u) вычисляет новый индекс hash("Bob") & mask и ищет в совершенно другой корзине.
Элемент невозможно найти или удалить, он навсегда застревает в куче, создавая утечку памяти.

[!IMPORTANT] Production Best Practice: Элементами Set обязаны быть строго неизменяемые объекты (Immutable) — примитивные обертки, String, либо Java record.

2. Конфликт `compareTo()` против `equals()` в `TreeSet`

Спецификация TreeSet содержит важнейшее отличие: он полностью игнорирует методы hashCode() и equals()!

Уникальность элементов в TreeSet проверяется исключительно условием: $\text{comparator.compare}(a, b) == 0 \quad \text{или} \quad a\text{.compareTo}(b) == 0$

record Product(int id, String title) implements Comparable<Product> {
    // equals сравнивает и id, и title:
    // compareTo сравнивает ТОЛЬКО id:
    @Override
    public int compareTo(Product o) {
        return Integer.compare(this.id, o.id);
    }
}

Set<Product> set = new TreeSet<>();
set.add(new Product(1, "Книга"));
set.add(new Product(1, "Телефон")); // НЕ ДОБАВИТСЯ! compareTo вернул 0.

System.out.println(set.size()); // 1!

Если логика compareTo не согласована с equals (consistent with equals), коллекция нарушает общий контракт Set, теряя данные с несовпадающими полями.

3. Интеграция с Java 21 `SequencedSet`

Начиная с Java 21 (JEP 431), коллекции с гарантированным порядком получили общий интерфейс SequencedSet:

LinkedHashSet и TreeSet теперь реализуют SequencedSet: они поддерживают getFirst(), getLast(), addFirst(), addLast() и reversed().
HashSet не реализует SequencedSet, так как порядок его элементов хаотичен.

🎯 Шпаргалка для интервью

30-секундный ответ для собеседования

«HashSet — это хэш-таблица ($O(1)$), порядок элементов которой не гарантирован и зависит от хэш-кодов. LinkedHashSet расширяет HashSet, связывая элементы двусвязным списком, что гарантирует обход строго в порядке вставки за счет чуть большего расхода памяти. TreeSet построен на красно-черном дереве ($O(\log N)$), автоматически сортирует элементы и поддерживает диапазонные запросы, но не поддерживает null и проверяет уникальность через compareTo(), а не equals(). В Java 21 LinkedHashSet и TreeSet реализуют интерфейс SequencedSet».

Вопросы повышенной сложности с ответами

Почему итерация по HashSet может оказаться катастрофически медленнее итерации по LinkedHashSet? Ответ: Итератор HashSet имеет сложность $O(\text{capacity} + \text{size})$. Он вынужден последовательно перебирать все ячейки внутреннего массива корзин Node[] table, даже если большинство из них пусты. Если хэш-таблица была выделена с запасом (например, емкость 1 000 000), а элементов в ней всего 10, итерация по HashSet проверит миллион бакетов. LinkedHashSet хранит элементы в сквозном двусвязном списке, и его итератор идет только по существующим узлам со сложностью $O(\text{size})$, пропуская пустые корзины.
Почему в TreeSet запрещено добавлять null, тогда как в HashSet разрешено? Ответ: HashSet кладет элементы в хэш-таблицу, где для null выделен специальный фиксированный нулевой бакет (hash = 0), а методы hashCode() и equals() на самом объекте не вызываются. TreeSet строит бинарное дерево поиска и при вставке обязан вызвать comparator.compare(e1, e2) или ((Comparable) e1).compareTo(e2). Попытка вызова метода сравнения на объекте null (или передачи null в компаратор) гарантированно выбрасывает NullPointerException.
Что произойдет, если вставить в HashSet и TreeSet два объекта, у которых метод equals() возвращает false, но compareTo() возвращает 0? Ответ: В HashSet будут успешно сохранены оба объекта, так как HashSet проверяет уникальность по цепочке: равенство хэш-кодов и вызов equals() == false. В TreeSet второй объект добавлен не будет, так как TreeSet проверяет уникальность исключительно через compareTo() == 0 и полностью игнорирует метод equals().
Что происходит при изменении полей объекта, уже находящегося внутри HashSet? Ответ: Если изменившиеся поля влияют на результат вычисления hashCode(), объект окажется в несогласованном состоянии. Его хэш-код изменится, но физически в хэш-таблице он останется лежать в старой корзине, вычисленной при добавлении. В результате метод contains() вернет false (так как будет искать в другой корзине), метод remove() не сможет его удалить, и в приложении возникнет утечка памяти.

Типичные ошибки и Red Flags

❌ Утверждать, что TreeSet проверяет уникальность через hashCode() и equals(). (Грубейший Red Flag: TreeSet использует строго Comparable/Comparator).
❌ Думать, что HashSet сохраняет порядок добавления элементов. (Порядок вставки сохраняет только LinkedHashSet).
❌ Помещать мутабельные объекты в качестве элементов множества. (Риск потери элементов и утечки памяти).

🟢 Junior Level

🟡 Middle Level

1. Архитектурное устройство под капотом

2. Парадокс производительности итерации: HashSet против LinkedHashSet

3. Навигационные возможности TreeSet