🟢 Junior Level

Bucket (корзина) — це елемент масиву table[] всередині HashMap.

Аналогія: Уявіть поштову шафу з комірками: масив — це вся шафа, бакет — конкретна комірка. Але на відміну від реальної комірки, в бакет можна покласти скільки завгодно елементів — вони вишиковуються в ланцюжок (linked list).

Коли HashMap хоче покласти елемент, вона обчислює номер корзини за формулою:

index = (розмір_таблиці - 1) & hash(ключа)

Приклад:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100); // Потрапив в корзину X (залежить від hashCode("key1"))
map.put("key2", 200); // Потрапив в корзину Y (залежить від hashCode("key2"))

Проста аналогія: Поштовий індекс визначає, на яке поштове відділення (бакет) відправити листа. А вже всередині відділення шукають конкретного отримувача.

🟡 Middle Level

Три стани бакета

1. Порожній (Empty) — комірка містить null. Займає тільки пам’ять під вказівник (4-8 байт).
2. Зв’язний список (Linked List) — при колізіях ноди зв’язуються через поле next. Пошук: O(k), де k — кількість елементів в бакеті.
3. Дерево (Tree) — при 8+ елементах і capacity >= 64 список перетворюється на червоно-чорне дерево (TreeNode, Java 8+). Пошук: O(log k).

Чому бакетів завжди 2^n?

Це фундаментальне архітектурне рішення:

• Формула index = (n-1) & hash коректно розподіляє елементи тільки при степені двійки
• При resize (подвоєнні) елементи або залишаються на місці, або переміщуються на index + oldCap — без повного перерахунку хешу

Параметри, що впливають на бакети

Параметр	Значення за замовчуванням	Вплив
Initial Capacity	16	Початкова кількість бакетів
Load Factor	0.75	При якому заповненні бакети подвоюються

Типова помилка: Не враховувати, що new HashMap(10) створить 16 бакетів (найближчий степінь двійки вгору).

Коли НЕ використовувати великий initialCapacity

Не задавайте надмірний initialCapacity: HashMap на 1 000 000 бакетів з 10 елементами витрачає ~8 МБ пам’яті марно (масив посилань на null).

🔴 Senior Level

Internal Implementation

Бакет — це елемент масиву Node<K,V>[] table. Кожен Node містить:

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Наступний елемент в ланцюжку колізій
}

При treeification бакет зберігає TreeNode:

class TreeNode<K,V> {
    TreeNode<K,V> parent, left, right, prev;
    boolean red;
    // + успадковує hash, key, value, next від Node
}

TreeNode займає ~2x більше пам’яті через додаткові посилання і прапорець кольору.

Розподіл Пуассона

Розподіл Пуассона — статистична модель, що описує ймовірність рідкісних подій. Ймовірність потрапляння 8+ елементів в один бакет при хорошому hashCode ≈ 0.00000006 — практично нульова.

При loadFactor 0.75 ймовірність кількості елементів в бакеті підпорядковується розподілу Пуассона:

• 0 елементів: ~22%
• 1 елемент: ~33%
• 2 елементи: ~25%
• 8 елементів: ~0.00000006 (майже неможливо при хорошому hashCode)

Поріг 8 для treeification обрано саме на основі цієї статистики.

Hash Flooding Attack

Якщо зловмисник підбере ключі з однаковим хешем, всі елементи потраплять в один бакет. До Java 8 це призводило до O(n) і DoS-атаки. Treeification (O(log n) нівелює цю загрозу.

Cache Locality

Бакети розкидані за різними адресами в Heap. Довгі ланцюжки ведуть до частих Cache Miss, оскільки кожна Node — окремий об’єкт. Це впливає на реальну продуктивність більше, ніж асимптотична складність.

Memory Implications

• Порожній бакет: 4-8 байт (залежить від UseCompressedOops)
• Node в списку: ~32-48 байт
• TreeNode: ~64-80 байт
• При capacity=16: ~128 байт на сам масив (16 посилань)

Production Monitoring

Для діагностики проблем з бакетами можна використовувати reflection або instrumentation для аналізу розподілу елементів по бакетах. У production аномальна кількість елементів в одному бакеті вказує на поганий hashCode() ключа.

---

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

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

• Bucket = елемент масиву table[], зберігає список або дерево елементів
• Три стани: порожній, зв’язний список, дерево (TreeNode при 8+ елементах і capacity >= 64)
• Capacity завжди степінь двійки — для формули index = (n-1) & hash
• При resize елементи або залишаються на місці, або зміщуються на index + oldCap
• Не задавайте надмірний initialCapacity — порожні бакети витрачають пам’ять
• Розподіл Пуассона: ймовірність 8+ елементів в бакеті ≈ 0.00000006

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

• Що буде при new HashMap(10)? — capacity стане 16 (найближчий степінь двійки)
• Чому treeification при 8, а не 4? — для k ≤ 7 список швидший за дерево (менше overhead)
• Скільки пам’яті займає порожній бакет? — 4-8 байт (посилання на null)
• Що таке treeification? — конвертація списку в червоно-чорне дерево при 8+ колізіях

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

• «Бакет зберігає тільки один елемент» — ні, при колізіях — список/дерево
• «HashMap створює масив при конструкторі» — ні, лінива ініціалізація (Java 8+)
• «При 8 елементах завжди дерево» — тільки якщо capacity >= 64

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

• [[1. Як влаштований HashMap всередині]]
• [[3. Як HashMap визначає, в який bucket покласти елемент]]
• [[6. Що відбувається при досягненні 8 елементів в одному bucket]]
• [[17. Що таке capacity в HashMap]]