🟢 Junior Level

HashSet, LinkedHashSet та TreeSet — три реалізації Set (колекція унікальних елементів).

Головна різниця:

	HashSet	LinkedHashSet	TreeSet
Порядок	Немає	Порядок додавання	Сортування
Швидкість	Швидка O(1) хеш-таблиця	Середня O(1) + оверхед зв’язного списку	Повільніша O(log n) червоно-чорне дерево
null	✅ Можна	✅ Можна	❌ Не можна

Приклад:

// HashSet: без порядку
Set<String> hs = new HashSet<>();
hs.add("C"); hs.add("A"); hs.add("B");
// Порядок залежить від hashCode() — може відрізнятися на різних JVM!
// → [A, C, B] (порядок не гарантований)

// LinkedHashSet: порядок додавання
Set<String> lhs = new LinkedHashSet<>();
lhs.add("C"); lhs.add("A"); lhs.add("B");
// → [C, A, B] (як додали)

// TreeSet: сортування
Set<String> ts = new TreeSet<>();
ts.add("C"); ts.add("A"); ts.add("B");
// → [A, B, C] (відсортовано!)

---

🟡 Middle Level

HashSet

// Всередині: HashMap
// Складність: O(1) для add/remove/contains
Set<String> set = new HashSet<>();

// ⚠️ Порядок залежить від hashCode()
// При resize порядок може змінитися!

// Ітерація: O(capacity + size)
// → Порожній HashSet(1_000_000) → повільна ітерація!

LinkedHashSet

// Всередині: LinkedHashMap
// Складність: O(1) для add/remove/contains
// + двозв'язний список для порядку

Set<String> set = new LinkedHashSet<>();
// Зберігає порядок ВСТАВКИ

// Ітерація: O(size) — швидша за HashSet!
// → Не залежить від capacity
// HashSet проходить по ВСІМ корзинам включаючи порожні (O(capacity + size)). LinkedHashSet йде тільки по елементах зв'язного списку (O(size)). При малому заповненні різниця помітна.

// Пам'ять: +2 посилання на елемент (next, before)

TreeSet

// Всередині: TreeMap (червоно-чорне дерево)
// Складність: O(log n) для всіх операцій
Set<String> set = new TreeSet<>();

// Навігація:
set.add("A"); set.add("C"); set.add("E");
set.floor("D");   // → "C" (найближчий менший)
set.ceiling("D"); // → "E" (найближчий більший)
set.subSet("A", "D"); // → [A, C] (діапазон)

Коли що використовувати

Сценарій	Що обрати
Унікальність, швидкість	HashSet
Унікальність + порядок вставки	LinkedHashSet
Сортування + діапазони	TreeSet
Кеш з порядком доступу	LinkedHashMap (accessOrder=true), НЕ LinkedHashSet

Пастка: мутабельні елементи

// ❌ Небезпечно!
Set<Person> set = new HashSet<>();
Person p = new Person("Ivan");
set.add(p);
p.setName("Petr");  // hashCode() змінився!
set.contains(p);    // → FALSE! Об'єкт "втрачений"

// ✅ Використовуйте immutable об'єкти
record Person(String name) {}  // Immutable!

---

Коли НЕ використовувати

• HashSet: якщо потрібен порядок ітерації — використовуйте LinkedHashSet
• LinkedHashSet: якщо пам’ять обмежена (+50% оверхед зв’язного списку) — використовуйте HashSet
• TreeSet: якщо не потрібне сортування (у 50 разів повільніший за HashMap) — використовуйте HashSet

---

🔴 Senior Level

Memory Footprint

HashSet (64-bit JVM, Compressed OOPs):
  Node: 32 байти оверхеду на елемент

LinkedHashSet:
  Node: 48 байт (додаткові next/before)

TreeSet:
  Entry: 40+ байт (left, right, parent, color)

→ Для 1 млн Long:
  HashSet: ~36 МБ
  LinkedHashSet: ~52 МБ
  TreeSet: ~44 МБ

Java 21: SequencedSet

// LinkedHashSet та TreeSet → SequencedSet
LinkedHashSet<String> set = new LinkedHashSet<>();
set.addFirst("A");    // Новий метод!
set.addLast("Z");     // Новий метод!
set.getFirst();       // Новий метод!
set.reversed();       // Зворотний порядок (view)

// HashSet НЕ SequencedSet (немає порядку)

HashSet Iterator O(capacity + size)

// ❌ Повільно: capacity 1 млн, size 10
HashSet<String> set = new HashSet<>(1_000_000);
for (int i = 0; i < 10; i++) set.add("x");

for (String s : set) { ... }
// → Пройде по 1 млн корзин!

// ✅ LinkedHashSet: O(size) = 10 ітерацій

LRU Cache на LinkedHashSet

// LinkedHashMap з accessOrder = true
Map<K, V> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_SIZE;  // Видалити старий
    }
};

// get() переміщує елемент в кінець → LRU eviction

compareTo vs equals

// TreeSet використовує compareTo, НЕ equals!
class Person implements Comparable<Person> {
    String name;
    public int compareTo(Person o) {
        return name.compareTo(o.name);
    }
    public boolean equals(Object o) {
        return false;  // Інша логіка!
    }
}

// Якщо compareTo = 0 → елемент НЕ додасться
// Навіть якщо equals = false!

Production Experience

Реальний сценарій: HashSet ітерація вбила latency

• HashSet(10 млн capacity, 100 елементів)
• Ітерація: 50 мс (перебор 10 млн корзин!)
• Рішення: LinkedHashSet
• Результат: 0.01 мс (100 елементів)

Best Practices

1. HashSet — за замовчуванням для унікальності
2. LinkedHashSet — коли важливий порядок
3. TreeSet — для сортування та діапазонів
4. Immutable елементи — обов’язково!
5. initialCapacity для HashSet — уникайте resize
6. Java 21 → SequencedSet API
7. Примітиви → fastutil/Trove (менше пам’яті)

Резюме для Senior

• HashSet = O(1), немає порядку, ітерація O(capacity+size)
• LinkedHashSet = O(1), порядок вставки, ітерація O(size)
• TreeSet = O(log n), сортування, навігація, діапазони
• Memory: HashSet < TreeSet < LinkedHashSet
• SequencedSet (Java 21) → getFirst/reversed
• Immutable елементи — критично!
• compareTo ≠ equals → втрата даних у TreeSet

---

🎯 Шпаргалка для інтерв’ю

Обов’язково знати:

• HashSet = O(1), немає порядку, всередині HashMap, ітерація O(capacity + size)
• LinkedHashSet = O(1), порядок вставки, всередині LinkedHashMap, ітерація O(size)
• TreeSet = O(log n), сортування, всередині TreeMap (червоно-чорне дерево), навігація (floor/ceiling/subSet)
• LinkedHashSet зберігає порядок через двозв’язний список (+2 посилання на елемент)
• HashSet ітерація проходить по ВСІМ корзинам включаючи порожні — LinkedHashSet тільки по елементах
• TreeSet використовує compareTo для унікальності, а не equals
• Мутабельні елементи небезпечні: зміна hashCode() після додавання = втрата елемента
• Java 21: SequencedSet API (getFirst, addLast, reversed) для LinkedHashSet та TreeSet

Часті уточнюючі запитання:

• Чому HashSet повільніше ітерується при великій ємності? — Тому що проходить по всім корзинам (O(capacity + size)), включаючи порожні. LinkedHashSet йде тільки по зв’язному списку (O(size)).
• Коли TreeSet НЕ прийме елемент? — Коли compareTo повертає 0, навіть якщо equals повертає false.
• Що станеться якщо змінити елемент у HashSet після додавання? — hashCode() зміниться, елемент опиниться в «неправильній» корзині — contains поверне false.
• Який Set обрати для LRU кешу? — LinkedHashMap з accessOrder=true та перевизначеним removeEldestEntry.

Червоні прапорці (НЕ говорити):

• ❌ «TreeSet використовує equals для перевірки унікальності» — використовує compareTo!
• ❌ «HashSet зберігає порядок вставки» — ні, порядок не гарантований
• ❌ «Можна безпечно змінювати mutable елементи у Set» — це ламає hashCode/equals контракт
• ❌ «LinkedHashSet повільніший за HashSet для всіх операцій» — тільки для пам’яті, складність та сама O(1)

Пов’язані теми:

• [[12. Як працює HashSet всередині]]
• [[13. Що таке TreeSet і як він працює]]
• [[15. В чому різниця між HashMap, LinkedHashMap та TreeMap]]
• [[14. Що таке Map і які реалізації існують]]