Як влаштований HashMap всередині

Всередині HashMap складається з масиву кошиків / бакетів (Node[] table), розмір якого завжди дорівнює степеню двійки ($16, 32, 64\dots$). Під час додавання пари за ключем о...

🟢 Junior Level

Короткий опис для співбесіди (30 секунд)

HashMap — це асоціативний масив (структура «ключ-значення»), в основі якого лежить геш-таблиця з відкритим гешуванням і методом ланцюжків (Separate Chaining).

Всередині HashMap складається з масиву кошиків / бакетів (Node<K,V>[] table), розмір якого завжди дорівнює степеню двійки ($16, 32, 64\dots$). Під час додавання пари за ключем обчислюється його геш-код, який перетворюється на індекс масиву за допомогою швидкої бітової маски: index = (n - 1) & hash. Якщо комірка вільна, туди записується вузол Node. У разі виникнення колізії (два різні ключі потрапили в один індекс) елементи організуються в однозв’язний список. Починаючи з Java 8, якщо довжина списку в одному кошику досягає 8 елементів, а загальний розмір таблиці не менший ніж 64, список трансформується у збалансоване червоно-чорне дерево (TreeNode), що гарантує швидкість пошуку $O(\log n)$ навіть за катастрофічної кількості колізій.

Порівняльна таблиця структур Map в Java

Реалізація Map	Внутрішня структура	Часова складність	Гарантія порядку елементів	Потокобезпечність
`HashMap`	Масив + списки + червоно-чорні дерева	$O(1)$ у середньому, $O(\log n)$ у найгіршому	❌ Немає порядку	❌ Ні (Fail-Fast)
`LinkedHashMap`	Геш-таблиця + двозв’язний список нод	$O(1)$	✅ Порядок вставки (або доступу)	❌ Ні
`TreeMap`	Червоно-чорне дерево (Red-Black Tree)	$O(\log n)$ завжди	✅ За ключем (`Comparable`/`Comparator`)	❌ Ні
`ConcurrentHashMap`	Масив бакетів + CAS + `synchronized` на ноду	$O(1)$	❌ Немає порядку	✅ Так (Thread-safe)

Базовий приклад у Java 21

import java.util.HashMap;
import java.util.Map;

public class HashMapBasicsDemo {
    public static void main(String[] args) {
        // Конструктор за замовчуванням: capacity = 16, loadFactor = 0.75
        // Важливо: до першого put() масив table дорівнює null (лінива алокація пам'яті)!
        Map<String, Integer> userAges = new HashMap<>();

        // 1. Додавання елементів (put)
        userAges.put("Alice", 30); // Геш ключа -> обчислення індексу -> запис ноди
        userAges.put("Bob", 25);
        userAges.put(null, 99);    // null-ключ завжди потрапляє в table[0]

        // 2. Отримання елемента (get)
        System.out.println("Вік Alice: " + userAges.get("Alice")); // O(1)

        // 3. Перезапис значення (при збігу hash та equals)
        userAges.put("Alice", 31); // Замінює 30 на 31, повертає старе значення 30

        System.out.println("Розмір мапи: " + userAges.size());
    }
}

🟡 Middle Level

Життєвий цикл операції `put(key, value)`

Алгоритм вставки елемента в HashMap в OpenJDK HotSpot складається з таких послідовних кроків:

                  put(key, value)
                         │
                         ▼
             key == null ? hash = 0 
        : hash = (h = key.hashCode()) ^ (h >>> 16)
                         │
                         ▼
               table == null або порожній?
              ├── Так ──► Виклик resize() (алокація масиву 16)
              └── Ні
                         │
                         ▼
             index = (table.length - 1) & hash
                         │
                         ▼
                  table[index] == null?
         ├── Так ──► Створити Node<K,V> і покласти в комірку
         └── Ні (КОЛІЗІЯ!)
                         │
                         ▼
             Перший вузол збігся за ключем?
     (p.hash == hash && (p.key == key || key.equals(p.key)))
         ├── Так ──► Перезаписати value
         └── Ні ──► Перевірити тип вузла:
                      ├── TreeNode ──► Вставка в червоно-чорне дерево
                      └── Node (Список) ──► Ітерація до кінця списку:
                             ├── Ключ знайдено ──► Оновити value
                             └── Досягнуто кінця ──► Вставити в хвіст
                                        │
                                        ▼
                            Довжина ланцюжка >= 8?
                          ├── Так ──► treeifyBin() (дерево або resize)
                          └── Ні ──► Завершити
                         │
                         ▼
        Інкремент modCount і size; size > threshold?
              ├── Так ──► Виклик resize() (подвоєння capacity)
              └── Ні ──► Завершити

Чому розмір таблиці завжди степінь двійки ($2^n$)

У вихідному коді HashMap індекс кошика обчислюється за формулою:

int index = (n - 1) & hash;

де $n$ — поточна місткість таблиці (table.length).

Математична причина:

Заміна ділення бітовою маскою: у математиці операція залишку від ділення $hash \pmod n$ на довільне число вимагає складної та повільної інструкції цілочисельного ділення процесора (idiv, що займає 20–40 тактів CPU). Якщо $n$ суворо є степенем двійки ($2^k$), то $hash \pmod{2^k}$ математично еквівалентний побітовій операції AND із числом $(2^k - 1)$, яка виконується процесором за 1 такт.
Рівномірність маски: якщо $n = 16$ (0001 0000_b), то $n - 1 = 15$ (0000 1111_b). Молодші 4 біти маски складаються лише з одиниць. Це гарантує, що кожен молодший біт гешу визначатиме підсумковий індекс. Якби місткість була непарним або довільним числом (наприклад, 15, маска 14 = 1110_b), молодший біт індексу завжди був би 0, і всі непарні кошики таблиці ніколи б не заповнилися.

Функція бітового перемішування (Hash Perturbation Function)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Навіщо потрібен зсув `h >>> 16` та XOR:

У стандартного об’єкта hashCode() повертає 32-бітний int. При малому розмірі мапи (наприклад, $n = 16$) маска (n - 1) = 15 враховує лише останні 4 молодші біти. Старші 28 бітів геш-коду у визначенні індексу взагалі не беруть участі!
Якщо у групи об’єктів молодші біти гешів випадково збігаються (а старші різняться), вони всі потраплять в один кошик, утворивши катастрофічну колізію.
Операція (h ^ (h >>> 16)) «підмішує» старші 16 бітів гешу в молодші. У результаті зміна будь-якого біта вихідного 32-бітного гешу впливає на вибір кошика.

🔴 Senior Level

HotSpot Memory Layout: Накладні витрати пам’яті

У корпоративних Highload-застосунках мільйони записів у HashMap створюють колосальний тиск на купу (Heap) через накладні витрати пам’яті:

Анатомія `Node<K, V>` у 64-бітній JVM з Compressed OOPs (`-XX:+UseCompressedOops`):

Object Header: 12 байтів (Mark Word 8 байтів + Compressed Klass Pointer 4 байти);
int hash: 4 байти;
final K key: 4 байти (стиснуте посилання);
V value: 4 байти (стиснуте посилання);
Node<K,V> next: 4 байти (стиснуте посилання на наступний елемент списку);
Padding (вирівнювання за 8 байтами): 4 байти.
Разом: рівно 32 байти пам’яті тільки на оболонку одного вузла Node (без урахування самих об’єктів ключа і значення)!

Анатомія `TreeNode<K, V>`:

TreeNode розширює LinkedHashMap.Entry, містячи посилання parent, left, right, prev і поле boolean red. Його розмір становить 56–64 байти (удвічі важчий за список).

Математика ресайзу в Java 8+: Bitwise Splitting без перегешування

У Java 7 під час збільшення місткості таблиці (resize()) відбувався повний перерахунок індексів кожного елемента через hash % newCapacity зі вставкою на початок зв’язного списку (що викликало зациклення потоків у багатопотоковому середовищі).

У Java 8+ алгоритм кардинально переписано: при подвоєнні місткості ($oldCap \to 2 \times oldCap$) у масці з’являється рівно один новий значущий біт на позиції $oldCap$.

oldCap = 16  (Маска: 0000 1111)
newCap = 32  (Маска: 0001 1111)
Різниця в масках — це біт 16 (0001 0000)

JVM перевіряє єдиний біт: (e.hash & oldCap) == 0:

Якщо дорівнює 0, індекс елемента в новій таблиці не змінюється (newIndex = oldIndex);
Якщо дорівнює 1, елемент зміщується рівно на величину старої місткості: newIndex = oldIndex + oldCap.

// З вихідного коду HashMap.resize():
Node<K,V> loHead = null, loTail = null; // Ланцюжок для старого індексу
Node<K,V> hiHead = null, hiTail = null; // Ланцюжок для індексу (oldIndex + oldCap)
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null) hiHead = e;
        else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

Елементи розділяються на дві черги зі збереженням оригінального порядку (Tail Insertion), що виключає нескінченні цикли.

Розподіл Пуассона та константа деревофікації 8

Чому для перетворення списку на дерево обрано поріг TREEIFY_THRESHOLD = 8?

У документації OpenJDK до класу HashMap наведено строгий математичний розрахунок на основі теорії ймовірностей. За ідеальної геш-функції та коефіцієнта завантаження $0.75$ розподіл елементів за кошиками підпорядковується розподілу Пуассона із середнім параметром $\lambda \approx 0.5$:

\[P(k) = \frac{e^{-\lambda} \lambda^k}{k!}\]

Ймовірність утворення кошика з $k$ елементами:

0 елементів: $0.6065$
1 елемент: $0.3032$
2 елементи: $0.0758$
3 елементи: $0.0126$
…
8 елементів: $0.00000006$ ($6 \times 10^{-8}$)

Ймовірність колізії глибиною 8 при чесному hashCode() становить менше ніж одна стомільйонна частка відсотка. Дерева були додані виключно як ешелонований захист від навмисних атак Hash Flooding DoS, коли зловмисник спеціально генерує ключі з однаковими гешами для деградації продуктивності сервера до $O(n)$.

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

1. 30-секундний есенс (Elevator Pitch)

HashMap — це геш-таблиця на основі масиву кошиків (Node<K,V>[] table), розмір якої завжди кратний степеню двійки. Індекс визначається бітовою операцією (n - 1) & hash, де hash отримано змішуванням старших і молодших 16 бітів вихідного hashCode(). Колізії вирішуються методом ланцюжків. Якщо довжина ланцюжка досягає 8, а розмір масиву $\ge 64$, список перебудовується в червоно-чорне дерево ($O(\log n)$). При ресайзі масив подвоюється, а елементи розділяються на старий і новий (oldIndex + oldCap) бакети перевіркою одного біта (hash & oldCap). HashMap не є потокобезпечною.

2. 4 каверзних питання з глибокими відповідями

Питання 1: Чому при досягненні 8 елементів у кошику дерево створюється не завжди, і яка друга умова обов’язково повинна виконатися?

Відповідь: Для перетворення списку на червоно-чорне дерево (метод treeifyBin()) повинні одночасно виконатися дві умови:

Довжина ланцюжка в конкретному бакеті $\ge 8$ (TREEIFY_THRESHOLD);
Загальна місткість масиву таблиці table.length $\ge 64$ (MIN_TREEIFY_CAPACITY).
Якщо в кошику накопичилося 8 елементів, але місткість таблиці менша ніж 64 (наприклад, 16 або 32), перетворення на дерево не відбувається. Натомість викликається метод resize(), який подвоює масив кошиків. Архітектори JDK виходили з того, що при малій таблиці колізія викликана просто нестачею кошиків, і ресайз розподілить елементи ефективніше, ніж створення важких об’єктів TreeNode.

Питання 2: Як працює оптимізація розділення бакета (`loHead`/`hiHead`) при ресайзі в Java 8+, і чому вона повністю усунула баг нескінченного циклу Java 7?

Відповідь: У Java 7 елементи при ресайзі вставлялися в голову нового списку (Head Insertion), що інвертувало порядок елементів. При стані гонки один потік міг переставити вказівники так, що посилання A.next = B перетворювалося на кільце B.next = A, приводячи до 100% завантаження CPU при наступному get().
У Java 8+ використовується хвостова вставка (Tail Insertion) і побітова перевірка (e.hash & oldCap) == 0. Список за один прохід розщеплюється на два незалежні зв’язні ланцюжки (lo — елементи, що залишаються на місці, та hi — елементи, що зміщуються на +oldCap) з повним збереженням вихідного порядку елементів, що виключає виникнення циклічних посилань.

Питання 3: Навіщо у функції `hash()` старші 16 бітів додаються через XOR з молодшими (`h ^ (h >>> 16)`)?

Відповідь: Масив HashMap за замовчуванням має невеликий розмір (16, 32, 64), тому маска (n - 1) залишає лише останні 4–6 молодших бітів гешу. Якщо ключі генерують геш-коди, у яких змінюються лише старші біти (наприклад, числа кратні 1000 або форматовані рядкові ID), без зсуву та XOR усі такі ключі даватимуть нульовий або однаковий індекс, створюючи критичні колізії. XOR зі зсувом на 16 бітів гарантує, що варіативність старших розрядів гешу відобразиться на молодших розрядах, забезпечуючи рівномірний розподіл за кошиками.

Питання 4: Чому як поріг зворотного перетворення дерева на список (`UNTREEIFY_THRESHOLD`) обрано значення 6, а не 7 чи 8?

Відповідь: Різниця між порогом деревофікації (8) та де-деревофікації (6) у 2 одиниці є гістерезисом (Hysteresis gap). Якби обидва пороги були рівними (наприклад, 8 для дерева і 7 для списку), то при частій циклічній вставці та видаленні 8-го елемента структура постійно здійснювала б дорогі перебудови дерева на список і навпаки (ефект Flapping / Churning). Зазор у 2 елементи запобігає частій зміні внутрішньої структури при невеликих коливаннях кількості даних.

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

❌ «У HashMap масив створюється одразу при виклику new HashMap<>().»
Правильно: Конструктор лише валідує loadFactor та initialCapacity. Сам масив table алокується ліниво — при першому виклику put() всередині методу resize().

❌ «Індекс кошика обчислюється через залишок від ділення hash % capacity.»
Правильно: Використовується побітове AND: (capacity - 1) & hash, що працює на порядки швидше за ділення.

❌ «Червоно-чорне дерево створюється завжди, як тільки в списку з’явилося 8 елементів.»
Правильно: Тільки якщо загальна місткість таблиці table.length >= 64. Інакше відбувається виклик resize().