В чому різниця між HashSet, LinkedHashSet та TreeSet

Інтерфейс Set представляє колекцію унікальних елементів (дублікати суворо заборонені). У стандартній бібліотеці Java існують три основні реалізації Set, які відрізняються впоряд...

🟢 Junior Level

Інтерфейс Set представляє колекцію унікальних елементів (дублікати суворо заборонені). У стандартній бібліотеці Java існують три основні реалізації Set, які відрізняються впорядкованістю, швидкістю операцій та внутрішньою організацією:

Характеристика	`HashSet`	`LinkedHashSet`	`TreeSet`
Порядок елементів	Не гарантований (хаотичний, залежить від хешу)	Порядок вставки (Insertion-Order)	Відсортований (Natural order або 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 комірок, витрачаючи мілісекунди CPU на порожній перебір!
Ітерація в 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