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

🟢 Junior Level

HashMap — це колекція в Java, яка зберігає дані у форматі “ключ-значення” (Map). Вона дозволяє дуже швидко знаходити, додавати і видаляти елементи за ключем.

Основна ідея: HashMap використовує хеш-таблицю — внутрішній масив бакетів (корзин).

Чому це швидко: На відміну від ArrayList, який перебирає всі елементи (O(n)), HashMap за хешем йде одразу в потрібну комірку — як за номером комірки камери сховища, а не перебираючи всі комірки поспіль. Коли ви додаєте елемент, HashMap обчислює спеціальний номер (хеш) ключа і визначає, в яку корзину його покласти. При пошуку вона знову обчислює цей хеш і йде одразу в потрібну корзину.

Приклад:

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);  // hashCode("Alice") = 63154590 → index = 15 → table[15]
ages.put("Bob", 25);    // hashCode("Bob") = 66133 → index = 5 → table[5]
System.out.println(ages.get("Alice")); // 30 — той самий хеш, той самий індекс 15

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

Коли потрібно швидко знаходити дані за ключем
Коли порядок елементів не важливий
Коли потрібен один з найшвидших варіантів для пошуку (в середньому O(1))

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

Потрібен порядок вставки — беріть LinkedHashMap
Потрібне сортування за ключем — TreeMap
Багатопотоковий доступ — ConcurrentHashMap
Критична пам’ять при малій кількості елементів — ArrayList з лінійним пошуком може бути економнішим

🟡 Middle Level

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

HashMap складається з кількох ключових полів:

transient Node<K,V>[] table; // Масив бакетів (ініціалізується ліниво при першому put)
int threshold;               // Поріг розширення (capacity * loadFactor)
final float loadFactor;      // Коефіцієнт завантаження (за замовчуванням 0.75)
transient int size;          // Поточна кількість елементів

Механіка put():

При першому put() створюється масив з 16 бакетів (лінива ініціалізація, Java 8+). У Java 7 масив створювався при конструюванні.
Обчислюється hash(key) — перемішаний (spread) хеш-код ключа.

Перемішування — старші біти хеш-коду ‘змішуються’ з молодшими через XOR. XOR — побітова операція: якщо біти різні → 1, однакові → 0. Це мінімізує колізії навіть при поганій hashCode-функції: різниця в старших бітах ‘переноситься’ в молодші, які використовуються для індексації.

Визначається індекс бакета: index = (n - 1) & hash
Якщо бакет порожній — створюється нова Node
Якщо бакет зайнятий — перевіряється equals() для пошуку наявного ключа
Якщо ключ знайдено — значення перезаписується, якщо ні — додається нова нода

Механіка get():

Обчислюється хеш ключа
Визначається індекс бакета
У бакеті шукається елемент через equals()

Типові помилки

Використання mutable-об’єктів як ключів — якщо змінити поля ключа після put(), елемент стане недоступним
Неперевизначений hashCode при перевизначеному equals — рівні об’єкти потраплять в різні бакети
Конкурентний доступ — HashMap не потокобезпечна

Порівняння з альтернативами

Реалізація	Складність пошуку	Порядок	Потокобезпечність
HashMap	O(1)	Немає	Ні
TreeMap	O(log n)	Сортування	Ні
LinkedHashMap	O(1)	Порядок вставки	Ні
ConcurrentHashMap	O(1)	Немає	Так

🔴 Senior Level

Internal Implementation

Функція хешування (spread):

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

Операція XOR між старшими і молодшими 16 бітами мінімізує колізії при невеликих масивах, де індекс визначається тільки молодшими бітами через маску (n-1).

Визначення індексу:

index = (n - 1) & hash;

Замість % використовується & — це працює в десятки разів швидше. Вимагає, щоб розмір масиву завжди був степенем двійки.

Архітектурні Trade-offs

Метод ланцюжків (Separate Chaining) vs Відкрита адресація:

HashMap використовує метод ланцюжків — колізії дозволяються зв’язними списками/деревами в кожному бакеті
✅ Плюси: стійкий до поганих хеш-функцій, простіше видалення
❌ Мінуси: алокує окремі об’єкти Node (накладні витрати на пам’ять, погана cache locality)
Відкрита адресація (як у ThreadLocalMap) економить пам’ять, але страждає від clustering

Treeification (Java 8+):

При 8 елементах в бакеті і capacity >= 64 зв’язний список перетворюється на червоно-чорне дерево.

Червоно-чорне дерево — збалансоване бінарне дерево пошуку, де кожна вершина ‘пофарбована’ в червоний або чорний колір. Правила розфарбування гарантують баланс: пошук завжди O(log n).

Гістерезис — зазор між порогами прямого (8 → дерево) і зворотного (6 → список) перетворення. Це запобігає ‘churn’ (дребезгу) — коли структура нескінченно перемикається туди-сюди при коливаннях навантаження.

Складність пошуку в найгіршому випадку: O(n) → O(log n)
TreeNode займає ~2x більше пам’яті, ніж Node
Поріг зворотного перетворення: 6 елементів (гістерезис для запобігання churn)

Edge Cases

Hash Flooding Attack — зловмисник підбирає ключі з однаковим хешем; до Java 8 це викликало DoS через O(n); у Java 8+ захист через treeification
Concurrent resize — у Java 7 при паралельному ресайзі виникало зациклення списку; у Java 8+ виправлено через tail insertion, але втрата даних все ще можлива
Null-ключ — завжди потрапляє в table[0], оскільки hash(null) = 0

Продуктивність

Середній випадок: O(1) для get/put/remove
Найгірший випадок: O(log n) (Java 8+), O(n) (Java 7)
Амортизована вартість put: O(1) (resize — O(n), але відбувається рідко)
Memory footprint: кожна Node — заголовок об’єкта + int hash + K key + V value + Node next ≈ 32-48 байт на запис (без урахування ключа/значення)

Resize Optimization

При подвоєнні масиву (Java 8+) не потрібно перераховувати хеши. Перевіряється один біт:

if ((e.hash & oldCap) == 0) {
    // Залишається на тому самому індексі
} else {
    // Переміщується на oldIndex + oldCapacity
}

Production Experience

У високонавантажених системах часті ресайзи викликають latency spikes. Рекомендується задавати initialCapacity = (expectedSize / 0.75) + 1, щоб уникнути O(n)-операцій в runtime.

Best Practices для Highload

Використовуйте ConcurrentHashMap для багатопотокового доступу
Попередньо розраховуйте capacity
Використовуйте імутабельні ключі з якісним hashCode
Уникайте null-ключів для кращої переносимості

🎯 Шпаргалка для співбесіди

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

HashMap = масив бакетів + зв’язні списки/дерева (Java 8+)
put/get працюють за O(1) в середньому випадку
Лінива ініціалізація: масив створюється при першому put
Spread-функція: XOR старших і молодших 16 біт для рівномірного розподілу
Індексація через (n-1) & hash — швидше за ділення
При 8 елементах в бакеті і capacity >= 64 — treeification (список → червоно-чорне дерево)
null-ключ допускається один, завжди в table[0]
Не потокобезпечна — для багатопотоковості ConcurrentHashMap

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

Чому capacity завжди степінь двійки? — щоб використовувати швидку бітову маску замість ділення
Що таке load factor 0.75? — баланс між пам’яттю і колізіями, обґрунтований розподілом Пуассона
Що буде при поганому hashCode? — всі елементи в одному бакеті, деградація до O(n) або O(log n)
Чому не використовувати HashMap в багатопотоковості? — data race, втрата даних, corruption при resize

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

«HashMap використовує ділення для індексації» — ні, бітова маска
«HashMap потокобезпечна» — ні, це ConcurrentHashMap
«При 8 елементах завжди дерево» — тільки якщо capacity >= 64

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

[[2. Що таке bucket (корзина) в HashMap]]
[[4. Що таке колізія в HashMap]]
[[5. Як HashMap обробляє колізії]]
[[16. Що таке load factor в HashMap]]
[[20. Яка тимчасова складність операцій get() і put() в HashMap]]