Як працює HashSet всередині?

🟢 Junior Level

HashSet всередині використовує HashMap!

// Всередині HashSet:
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

Як це працює:

Ваш елемент → ключ у HashMap
Значення → один і той самий об’єкт PRESENT
Унікальність → HashMap не допускає дублікатів ключів

Приклад:

HashSet<String> set = new HashSet<>();
set.add("A");
// Всередині: map.put("A", PRESENT)

set.add("A");
// Всередині: map.put("A", PRESENT) → вже є! → false

🟡 Middle Level

Чому через HashMap?

Переваги:
  → Один код для HashMap та HashSet
  → Всі покращення HashMap автоматично у HashSet
  → Java 8: Treeification — перетворення зв'язного списку у червоно-чорне дерево при > 8 елементів у корзині. Захист від деградації O(1) → O(n) при колізіях hashCode.

Пам’ять

Кожен елемент у HashSet:
  HashMap$Node:
    Header: 12 байт
    int hash: 4 байти
    K key: 4-8 байт (посилання)
    V value: 4 байти (посилання на PRESENT)
    Node next: 4-8 байт
    Padding: до 8 байт

Разом: ~32 байти оверхеду на елемент!

→ HashSet<Long> у 8 разів більший, ніж long[]

Колізії та Java 8+

Мало колізій (< 8 у корзині):
  → Зв'язний список
  → Пошук: O(n)

Багато колізій (> 8, розмір > 64):
  → Червоно-чорне дерево
  → Пошук: O(log n)

→ Захист від Hash DoS атак!

Серіалізація

// Поле map = transient (не серіалізується напряму). Причина: хеш-таблиця залежить від JDK-специфічного hashCode() та рандомізації — при десеріалізації на іншій JVM елемент потрапив би в іншу корзину. Замість цього HashSet серіалізує елементи та перестворює map.

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

// ❌ Втрата елемента
Person p = new Person("Ivan");
set.add(p);
p.setName("Petr");  // hashCode() змінився!
set.remove(p);      // → FALSE! Шукаємо не в тій корзині

// ✅ Immutable елементи
record Person(String name) {}

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

Потрібен порядок ітерації — використовуйте LinkedHashSet
Елементи з поганим hashCode — отримаєте O(n) замість O(1) (багато колізій)
Зберігаєте примітиви — використовуйте fastutil/eclipse-collections для економії пам’яті у 4 рази

🔴 Senior Level

Hash DoS Attack захист

Атака: зловмисник підбирає ключі з однаковим hashCode()
  → Всі в одну корзину
  → Пошук O(n) замість O(1)
  → Сервер "висне"

Java 8+: Treeification при > 8 елементів
  → Пошук O(log n) навіть при атаці
  → Хеш-функція з рандомізацією

Memory Deep Dive

HashSet<String> для 1 млн рядків:

1 млн HashMap$Node: 32 МБ
1 млн String об'єктів: ~40 МБ
1 млн char[] масивів: ~24 МБ
HashMap table array: ~4 МБ

Разом: ~100 МБ

→ ArrayList<String>: ~68 МБ
→ HashSet на 50% більший!

Load Factor trade-off

За замовчуванням: 0.75

Збільшити (0.9):
  → Менше пам'яті
  → Більше колізій
  → Повільніший пошук

Зменшити (0.5):
  → Більше пам'яті
  → Менше колізій
  → Швидший пошук

Альтернативи для примітивів

// ❌ HashSet<Long> для 100 млн елементів
// → 100 млн Node об'єктів → 3.2 ГБ!

// ✅ fastutil (відкрита адресація)
LongOpenHashSet set = new LongOpenHashSet();
// → Без Node об'єктів → 800 МБ
// → У 4 рази менше пам'яті!

Internal Structure

HashSet → AbstractSet → AbstractCollection

Делегування:
  add(e)         → map.put(e, PRESENT)
  remove(e)      → map.remove(e) == PRESENT
  contains(e)    → map.containsKey(e)
  size()         → map.size()
  iterator()     → map.keySet().iterator()
  clear()        → map.clear()

→ HashSet = тонка обгортка над keySet!

Production Experience

Реальний сценарій: Bad hashCode

Об’єкти з hashCode() = 0 для всіх
Всі в одну корзину → O(n) пошук
100,000 елементів → 5 секунд на contains!
Рішення: переписати hashCode()
Результат: 0.1 мс

Best Practices

Елементи повинні бути effectively immutable поки знаходяться у Set. Мутація елемента після додавання ламає hashCode/equals контракт — елемент стає «невидимим» для пошуку.
hashCode/equals контракт — критичний
initialCapacity — уникайте ресайзів
fastutil для примітивів
Treeification → індикатор поганого hashCode
Серіалізація — custom, не стандартна

Резюме для Senior

HashSet = обгортка над HashMap.keySet()
PRESENT = static final Object заглушка
Memory = ~32 байти оверхеду на елемент
Treeification = захист від Hash DoS (> 8)
Transient map = custom серіалізація
Mutable елементи = втрата даних!
Відкрита адресація = менше пам’яті (fastutil)

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

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

HashSet всередині — обгортка над HashMap.keySet(), кожен елемент = ключ, значення = static final Object PRESENT
Складність: O(1) для add/remove/contains у середньому випадку
Java 8+: treeification при > 8 елементів у корзині — зв’язний список перетворюється у червоно-чорне дерево (O(log n))
Memory overhead: ~32 байти на елемент (HashMap$Node: hash, key, value, next)
Load factor за замовчуванням 0.75 — баланс між пам’яттю та колізіями
Серіалізація custom: поле map = transient, елементи серіалізуються окремо
Мутабельні елементи ламають пошук — hashCode() змінюється, елемент «втрачається»
Для примітивів краще fastutil/Trove — відкрита адресація, у 4 рази менше пам’яті

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

Навіщо HashSet використовує HashMap, а не свою структуру? — Перевикористання коду, всі оптимізації HashMap автоматично доступні.
Що таке treeification та навіщо потрібна? — При > 8 колізій у корзині список перетворюється у дерево — захист від Hash DoS атак (O(n) → O(log n)).
Чому серіалізація custom? — Хеш-таблиця залежить від JVM-специфічного hashCode() та рандомізації — при десеріалізації елементи можуть потрапити в інші корзини.
Як зменшити memory footprint HashSet для примітивів? — Використовувати fastutil LongOpenHashSet та аналоги — без Node-об’єктів, відкрита адресація.

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

❌ «HashSet зберігає елементи напряму» — зберігає як ключі HashMap із заглушкою PRESENT
❌ «HashSet повністю thread-safe» — ні, потрібна ConcurrentHashMap або Collections.synchronizedSet
❌ «HashSet гарантує порядок ітерації» — порядок не гарантований, залежить від hashCode()
❌ «Treeification відбувається завжди при колізіях» — тільки при > 8 елементів І розмірі > 64

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

[[11. В чому різниця між HashSet, LinkedHashSet та TreeSet]]
[[14. Що таке Map і які реалізації існують]]
[[15. В чому різниця між HashMap, LinkedHashMap та TreeMap]]
[[19. Як ConcurrentHashMap забезпечує thread-safety]]