🟢 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 медленнее итерируется при большом capacity? — Потому что проходит по всем корзинам (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 и какие реализации существуют]]