📦 Розділ 4 · Питання #12

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

Клас HashSet у Java не реалізує власну низькорівневу структуру даних для зберігання елементів. Натомість він є елегантною та легковажною обгорткою над стандартним класом HashMap:

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

1. Архітектурна суть

Клас HashSet у Java не реалізує власну низькорівневу структуру даних для зберігання елементів. Натомість він є елегантною та легковажною обгорткою над стандартним класом HashMap:

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E, Object> map;
    
    // Фіктивний об'єкт-заглушка для значення кожного ключа
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }
}

Усі елементи, що додаються до HashSet, зберігаються виключно як ключі внутрішньої мапи HashMap. Оскільки HashMap фундаментально гарантує унікальність своїх ключів, HashSet автоматично забезпечує повну унікальність елементів множини.

Як значення (value) для всіх ключів підставляється одне й те саме статичне посилання-пустишка — PRESENT (new Object()).

HashSet: ["Apple", "Banana", "Cherry"]
  │
  ▼
HashMap (Внутрішнє представлення):
  ┌──────────┬─────────────────┐
  │   Key    │      Value      │
  ├──────────┼─────────────────┤
  │ "Apple"  │ ──► PRESENT     │
  │ "Banana" │ ──► PRESENT     │
  │ "Cherry" │ ──► PRESENT     │
  └──────────┴─────────────────┘

2. Базові операції та їх реалізація

Усі публічні методи HashSet просто делегують виконання внутрішньому екземпляру map:

// Додавання елемента:
// put() повертає null, якщо ключ новий, або попереднє значення (PRESENT), якщо ключ уже був.
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// Перевірка наявності:
public boolean contains(Object o) {
    return map.containsKey(o);
}

// Видалення:
// remove() повертає видалене значення (PRESENT) або null, якщо ключа не існувало.
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// Очищення та розмір:
public int size() {
    return map.size();
}

public void clear() {
    map.clear();
}

Часова складність основних операцій

Операція Середній випадок Найгірший випадок (усі колізії) Примітка
add(E e) $O(1)$ $O(\log N)$ / $O(N)$ $O(\log N)$ при трансформації в червоно-чорне дерево в Java 8+
contains(Object o) $O(1)$ $O(\log N)$ / $O(N)$ Залежить від рівномірності розподілу hashCode()
remove(Object o) $O(1)$ $O(\log N)$ / $O(N)$ Швидке видалення за хешем
Ітерація $O(\text{capacity} + N)$ $O(\text{capacity} + N)$ Обхід усього масиву бакетів, включно з порожніми

🟡 Middle Level

1. Обчислення індексу бакета та розв’язання колізій

Коли викликається set.add(e), внутрішня HashMap виконує наступну послідовність кроків:

  1. Хешування ключа (Perturbation Function): 
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    Зсув праворуч на 16 бітів та операція XOR підмішують старші біти хеш-коду до молодших. Це запобігає масовій кластеризації колізій, коли розмір таблиці невеликий (наприклад, 16), а молодші біти у ключів збігаються.

  2. Визначення індексу в масиві бакетів Node<K,V>[] table: 
    index = (table.length - 1) & hash;

    Розмір таблиці завжди є степенем двійки ($2^k$). Це дозволяє замінити повільне ділення за модулем % на швидке побітове AND за 1 машинний такт процесора.

  3. Пошук елемента в бакеті: Якщо в бакеті вже присутній вузол, HashMap перевіряє рівність ключів: 
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    Спочатку порівнюються значення hash (примітивний int), потім посилання через ==, і лише при незбігу посилань викликається важчий метод .equals().

2. Деревізація колізій (Treeification) у Java 8+

До Java 8 колізії в бакетах зберігалися виключно у вигляді однозв’язного списку (Node<K,V>). За навмисної атаки (Hash DoS) або невдалого алгоритму hashCode() пошук деградував до лінійного $O(N)$.

У Java 8+ впроваджено механізм деревізації (Treeification):

  • Умова перетворення на дерево: якщо в одному бакеті накопичується $\ge 8$ елементів (TREEIFY_THRESHOLD = 8) ТА загальна місткість масиву бакетів $\ge 64$ (MIN_TREEIFY_CAPACITY = 64).
  • Якщо елементів у кошику $\ge 8$, проте загальна місткість масиву $< 64$, дерево не створюється — замість цього викликається resize(), що подвоює розмір таблиці.
  • При деревізації зв’язний список замінюється збалансованим червоно-чорним деревом (TreeNode), знижуючи найгіршу складність пошуку з $O(N)$ до $O(\log N)$.
  • Зворотний перехід (Untreeify): якщо внаслідок видалення елементів або resize() розмір дерева зменшується до $\le 6$ (UNTREEIFY_THRESHOLD = 6), дерево перетворюється назад на звичайний зв’язний список.
Бакет із колізіями:
[0..7 елементів]: Node -> Node -> Node -> Node (Зв'язний список, O(N))
[>= 8 елементів + capacity >= 64]: TreeNode (Червоно-чорне дерево, O(log N))

3. Небезпека мутації об’єктів (Mutable Keys Trap)

Оскільки HashSet використовує елементи як ключі в HashMap, елементи множини зобов’язані бути незмінними (immutable) або принаймні їхні поля, що беруть участь у hashCode() та equals(), не повинні змінюватися під час перебування в сеті.

class User {
    private String name;
    public User(String name) { this.name = name; }
    public void setName(String name) { this.name = name; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User user)) return false;
        return Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

Set<User> users = new HashSet<>();
User ivan = new User("Іван");
users.add(ivan);

// Мутація об'єкта після додавання:
ivan.setName("Петро");

// КАТАСТРОФА:
System.out.println(users.contains(ivan)); // false!
users.remove(ivan);                       // false! (елемент не видалився)
System.out.println(users.size());         // 1 (об'єкт-зомбі застряг у сеті!)

Що відбулося під капотом:

  1. При додаванні об’єкт потрапив у бакет згідно зі старим hashCode("Іван").
  2. Після виклику setName("Петро") його hashCode() змінився.
  3. Під час перевірки contains(ivan) HashSet обчислює новий хеш-код і шукає в зовсім іншому бакеті. Бакет виявляється порожнім, повертається false.
  4. Об’єкт фізично залишається в старому бакеті, породжуючи прихований витік пам’яті (Memory Leak).

🔴 Senior Level

1. Детальний аналіз накладних витрат пам’яті (Memory Footprint)

HashSet споживає відчутну кількість пам’яті через об’єктну структуру вузлів HashMap$Node:

На 64-бітній JVM з увімкненим Compressed OOPs (-XX:+UseCompressedOops, діє за замовчуванням до 32 ГБ купи):

  • Заголовок Node (Header): 12 байтів (Mark Word 8 байтів + compressed Klass 4 байти).
  • Поля Node:
    • int hash: 4 байти.
    • K key (compressed ref): 4 байти.
    • V value (compressed ref): 4 байти.
    • Node<K,V> next (compressed ref): 4 байти.
  • Вирівнювання (Padding): доповнення до кратності 8 байтів $\to 4$ байти.
  • Разом розмір однієї ноди: 32 байти.
  • Посилання в масиві бакетів (table[i]): 4 байти на комірку (при loadFactor = 0.75 фактично $\approx 5.3$ байта на елемент).
Оверхед на 1 елемент HashSet: ~32 байти (нода) + ~5 байтів (бакет) = ~37 байтів чистої службової структури.
Сам об'єкт-елемент (наприклад, Long) вимагає ще 24 байти (16 байтів заголовок + 8 байтів value).

Для зберігання 10 000 000 чисел long:

  • HashSet<Long>: займе $\approx 610$ МБ купи та породить 20 мільйонів об’єктів (10 млн Long + 10 млн Node).
  • Спеціалізована колекція примітивів із відкритою адресацією (it.unimi.dsi.fastutil.longs.LongOpenHashSet): зберігає дані в пласкому масиві long[] без об’єктів-обгорток і нод. Вона потребує всього $\approx 80$ МБ ($\approx$ у 7.5 раза менше) і створить рівно 0 об’єктів для GC!

2. Особливості серіалізації: чому map оголошено як transient?

У класі HashSet внутрішня мапа оголошена з модифікатором transient:

private transient HashMap<E, Object> map;

Причина: Хеш-таблиця прив’язана до конкретної реалізації hashCode() та архітектури JVM. Зокрема, хеш-коди деяких класів (наприклад, IdentityHashMap або системний identityHashCode) залежать від фізичної адреси об’єкта в пам’яті. Крім того, при розгортанні застосунку на іншій версії JDK чи на іншій архітектурі процесора розподіл за бакетами може змінитися.

Якби HashSet напряму серіалізував масив бакетів table, при десеріалізації на іншій JVM елементи потрапили б не в ті бакети, що зруйнувало б логіку роботи множини.

Рішення через кастомну серіалізацію: HashSet реалізує приватні методи writeObject та readObject:

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());
    s.writeInt(map.size());

    // Серіалізуються ТІЛЬКИ самі елементи, без структури бакетів і без нод!
    for (E e : map.keySet())
        s.writeObject(e);
}

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    // Читаються параметри місткості та коефіцієнта завантаження
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
    map = new HashMap<>(capacity, loadFactor);

    int size = s.readInt();
    // Кожен елемент заново вставляється через map.put()
    for (int i = 0; i < size; i++) {
        @SuppressWarnings("unchecked")
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

3. Прихований пакетно-приватний конструктор для LinkedHashSet

У вихідному коді HashSet є неочевидний конструктор із модифікатором package-private:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

Він використовується виключно спадкоємцем LinkedHashSet. Булевий аргумент dummy слугує лише маркером для перевантаження сигнатури конструктора. Це архітектурне рішення дозволило розробникам JDK повторно використати весь код HashSet для LinkedHashSet, підмінивши базову реалізацію HashMap на LinkedHashMap.

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

30-секундна відповідь (Elevator Pitch)

«HashSet — це тонка обгортка над HashMap, що реалізує інтерфейс Set. Додані елементи стають ключами внутрішньої хеш-таблиці, а як значення підставляється єдиний статичний фіктивний об’єкт-заглушка PRESENT (new Object()). Завдяки цьому HashSet забезпечує середню складність $O(1)$ для операцій add, remove та contains. У Java 8+ при великій кількості колізій ($\ge 8$ елементів у бакеті та capacity $\ge 64$) зв’язний список бакета трансформується в червоно-чорне дерево, обмежуючи найгірший час пошуку до $O(\log N)$».

3 каверзних питання на інтерв’ю з відповідями

1. Чому HashSet не має власного методу get(Object o)?

Відповідь: За контрактом множини елемент або присутній, або відсутній (contains(o)). Якщо у вас уже є об’єкт o, рівний шуканому за equals(), викликати get() не має практичного сенсу, оскільки об’єкт уже у ваших руках. Якщо ж потрібне зіставлення ключа з об’єктом-сховищем (наприклад, інтернування або кешування), слід використовувати Map<K, V>.

2. Що станеться, якщо в клас елемента HashSet не імплементувати Comparable, але в одному бакеті виникне понад 8 колізій?

Відповідь: Відбудеться деревізація (при capacity $\ge 64$). Червоно-чорне дерево спробує порівнювати ключі через Comparable.compareTo(). Якщо клас ключа не реалізує Comparable, HashMap звертається до методу tieBreakOrder(Object a, Object b), який порівнює імена класів через a.getClass().getName().compareTo(...), а при збігу імен класів — системні хеші через System.identityHashCode(a). Дерево буде побудовано, але з меншою ефективністю операцій порівняння.

3. Чому створення new HashSet<>(1_000_000) без додавання елементів може суттєво уповільнити програму?

Відповідь: Ініціалізація виділить масив бакетів table на $2^{20} = 1\,048\,576$ комірок ($\approx 4$ МБ посилань). Головна пастка — подальша ітерація: ітератор HashSet має складність $O(\text{capacity} + N)$. Щоб обійти колекцію з 0 або 10 елементами, ітератор буде змушений послідовно перевірити всі 1 048 576 комірок масиву в пошуках непорожніх бакетів, що призведе до тисяч промахів процесорного кешу (Cache Misses).

Типові помилки та Red Flags

  • ❌ Мутація полів об’єкта після додавання в Set: Зміна полів, що впливають на hashCode(), робить об’єкт невидимим для contains() і неможливим для видалення через remove(), породжуючи витік пам’яті.
  • ❌ Неузгодженість equals() та hashCode(): Порушення контракту веде до появи дублікатів у множині або неможливості знайти доданий елемент.
  • ❌ Використання HashSet<Long> або HashSet<Integer> для мільйонів примітивів: Створює колосальний оверхед пам’яті ($\approx 37$ байтів на ноду + 24 байти на боксинг). Для примітивів слід використовувати спеціалізовані бібліотеки (fastutil, eclipse-collections).
  • ❌ Твердження, що HashSet є потокобезпечним: HashSet не синхронізований. Одночасні читання та запис можуть призвести до пошкодження внутрішньої структури даних. У конкурентному середовищі необхідний ConcurrentHashMap.newKeySet() або Collections.synchronizedSet().

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