Що таке бакет в HashMap

Сам масив table являє собою геш-таблицю, а його довжина (table.length) називається місткістю (capacity). Кожен бакет зберігає або null (якщо кошик порожній), або посилання на пе...

🟢 Junior Level

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

Bucket (кошик / бакет) у HashMap — це окрема комірка внутрішнього масиву Node<K,V>[] table.

Сам масив table являє собою геш-таблицю, а його довжина (table.length) називається місткістю (capacity). Кожен бакет зберігає або null (якщо кошик порожній), або посилання на перший елемент колекції, що потрапив за цим індексом. Якщо в один і той самий кошик потрапляють кілька елементів з однаковим обчисленим індексом (колізія), вони об’єднуються в однозв’язний список через посилання next. Якщо кількість елементів в одному кошику досягає 8 (при розмірі таблиці не менше ніж 64), бакет перебудовується у збалансоване червоно-чорне дерево (TreeNode).

Порівняльна таблиця станів кошика (Bucket States)

Стан кошика	Внутрішнє представлення	Споживання пам’яті (RAM)	Часова складність пошуку
1. Порожній (Empty)	`table[i] == null`	4 або 8 байтів (посилання в масиві)	$O(1)$ — миттєва перевірка на `null`
2. Одиничний вузол (Single Node)	`Node<K,V>` без продовження (`next == null`)	32 байти (вузол) + посилання на ключ/значення	$O(1)$ — перевірка одного ключа
3. Зв’язний список (Collision List)	Ланцюжок вузлів `Node<K,V>` (від 2 до 7 елементів)	По 32 байти на кожен вузол списку	$O(k)$, де $k$ — глибина колізії ($k \le 7$)
4. Червоно-чорне дерево (Treeified)	Дерево `TreeNode<K,V>` ($\ge 8$ елементів)	~56–64 байти на кожен вузол дерева	$O(\log k)$ — логарифмічний пошук

Демонстрація в Java 21

import java.util.HashMap;

public class BucketInspectionDemo {
    public static void main(String[] args) {
        // Створюємо мапу (масив table поки що дорівнює null!)
        HashMap<String, String> map = new HashMap<>();

        // При першому put() створюється масив table[] довжиною 16 бакетів (індекси 0..15)
        map.put("Java", "Language");
        map.put("Kotlin", "Language");

        // Індекс кошика розраховується за формулою: index = (table.length - 1) & hash
        // null-ключ завжди потрапляє в кошик з індексом 0:
        map.put(null, "DefaultValue");

        System.out.println("Кількість елементів у мапі: " + map.size());
    }
}

🟡 Middle Level

Математика адресації кошика: чому місткість завжди $2^n$

Індекс кошика, в який поміщається елемент, обчислюється за формулою:

int index = (table.length - 1) & hash;

Навіщо потрібен степінь двійки:

Апаратне прискорення: ділення процесора (idiv) займає десятки тактів, тоді як бітове AND виконується за 1 такт.
Повнота покриття: число $(2^n - 1)$ у двійковій системі числення є суцільною послідовністю одиниць:
- $16 - 1 = 15 = 0000\,1111_b$
- $32 - 1 = 31 = 0001\,1111_b$
- $64 - 1 = 63 = 0011\,1111_b$
  Це гарантує, що кожен молодший біт гешу буде рівноправно брати участь у виборі індексу кошика.

Функція `tableSizeFor(int cap)`: Округлення місткості вгору

Якщо розробник створює мапу з довільним initialCapacity (наприклад, new HashMap<>(10)), JVM не створює масив із 10 комірок. Внутрішній алгоритм округлює передане число до найближчого степеня двійки вгору:

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

(У Java 8 використовувалася послідовність бітових зсувів n |= n >>> 1; n |= n >>> 2; ... n |= n >>> 16;, у сучасних версіях оптимізована через intrinsic numberOfLeadingZeros).

Вхідне значення: 10  ──► tableSizeFor(10)  ──► capacity = 16
Вхідне значення: 17  ──► tableSizeFor(17)  ──► capacity = 32
Вхідне значення: 500 ──► tableSizeFor(500) ──► capacity = 512

Правильний розрахунок `initialCapacity`

Якщо ви очікуєте зберегти в мапі 1000 елементів, наївна ініціалізація new HashMap<>(1000) призведе до зайвого ресайзу:

tableSizeFor(1000) округлить місткість до 1024;
Поріг розширення: threshold = 1024 * 0.75 = 768;
При вставці 769-го елемента відбудеться дорогий ресайз таблиці з подвоєнням до 2048!

Формула безконфліктної місткості:

$\text{initialCapacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil + 1 = \left\lceil \frac{1000}{0.75} \right\rceil + 1 = 1335 \longrightarrow 2048$ У Java 19+ для цього додано офіційний фабричний метод:

Map<String, User> userCache = HashMap.newHashMap(1000); // Сам розрахує місткість 2048!

🔴 Senior Level

Аналіз накладних витрат пам’яті: Heap vs Cache Locality

У високонавантажених системах критично розуміти, скільки фізичної пам’яті споживає сам масив кошиків:

Масив кошиків Node<K,V>[] table:
- Довжина масиву: N комірок
- Кожна комірка: посилання (4 байти при Compressed OOPs, 8 байтів без)
- Заголовок масиву в купі: 16 байтів

При capacity = 16: $16 \times 4 + 16 = 80$ байтів.
При надлишковому initialCapacity = 1_000_000: порожній масив займе ~4 МБ оперативної пам’яті, навіть якщо в нього додадуть лише 5 елементів!

Проблема Cache Locality у Separate Chaining:

HashMap використовує метод ланцюжків (Separate Chaining). На відміну від відкритої адресації (Open Addressing / Linear Probing), де всі дані зберігаються підряд у безперервному масиві (як у Python dict або спеціалізованих високопродуктивних колекціях Eclipse Collections / Agrona):

У Java HashMap вузли Node алокуються в довільних ділянках купи через new Node<>();
Обхід зв’язного списку в кошику під час колізії призводить до послідовних промахів кешу процесора (CPU Cache Misses);
Проте метод ланцюжків був обраний архітекторами Java через стійкість: він не деградує при коефіцієнтах завантаження $>0.7$ і не страждає від ефекту кластеризації (Primary Clustering), властивого відкритій адресації.

Аналіз аномалій розподілу: Skewed Buckets у Production

У продакшен-моніторингу перекіс розподілу за кошиками (коли 95% елементів збираються у 2–3 бакетах) свідчить про порушення контракту hashCode():

// Найгірший сценарій розподілу кошиків:
public class DefectiveKey {
    private final String id;
    public DefectiveKey(String id) { this.id = id; }
    
    // ❌ КАТАСТРОФА: усі елементи завжди потрапляють в один бакет (індекс = 0)!
    @Override
    public int hashCode() {
        return 42;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof DefectiveKey other && this.id.equals(other.id);
    }
}

У такій ситуації HashMap перетворюється на одне червоно-чорне дерево, деградуючи продуктивність до $O(\log n)$ з постійним перебалансуванням дерева при вставці.

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

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

Бакет (кошик) у HashMap — це комірка внутрішнього масиву Node<K,V>[] table, що адресується бітовою маскою (table.length - 1) & hash. Кошик може перебувати в 4 станах: порожній (null), одиничний вузол, зв’язний список (при колізіях до 7 елементів) та червоно-чорне дерево (TreeNode при $\ge 8$ елементах і місткості $\ge 64$). Місткість таблиці завжди кратна степеню двійки, а при створенні мапи через new HashMap<>(cap) значення округлюється вгору методом tableSizeFor(). Для уникнення ресайзу в Java 19+ рекомендується використовувати HashMap.newHashMap(n).

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

Питання 1: Що фізично зберігається в комірці `table[index]`, якщо в даний бакет потрапило кілька елементів з однаковим індексом?

Відповідь: У самій комірці масиву table[index] фізично зберігається звичайне посилання (вказівник) на перший вузол (голову) однозв’язного списку Node<K,V> (або корінь червоно-чорного дерева TreeNode<K,V>). Усі наступні елементи ланцюжка колізій прив’язані один до одного посиланнями node.next і фізично розподілені по купі JVM. Масив table не розширюється «вглиб», він містить строго плаский список вказівників.

Питання 2: Як метод `tableSizeFor(int cap)` перетворює довільне число на найближчий степінь двійки без циклів?

Відповідь: Метод бере передане число $cap - 1$ і обчислює кількість провідних нульових бітів за допомогою процесорної інструкції LZCNT / методу Integer.numberOfLeadingZeros(). Потім беззнаковий зсув -1 >>> leadingZeros заповнює всі розряди після старшого біта одиницями, перетворюючи число на маску вигляду 000...01111111. Додавання одиниці (+ 1) дає степінь двійки ($2^k$). Уся операція займає кілька тактів CPU без циклів та розгалужень.

Питання 3: Чому в Java `HashMap` використовується метод ланцюжків (Separate Chaining), а не метод відкритої адресації (Open Addressing)?

Відповідь: У відкритій адресації під час колізії елемент поміщається в наступну вільну комірку того самого масиву. Це дає ідеальну локальність даних у кеші CPU, але має фатальні недоліки:

Вимагає низького коефіцієнта завантаження (не більше ніж $0.5$), інакше продуктивність експоненціально падає через кластеризацію;
Видалення елементів вкрай дороге (вимагає надгробків TOMBSTONE та періодичної дефрагментації);
Метод ланцюжків з деревофікацією (Java 8+) гарантує передбачувану верхню межу $O(\log n)$ навіть при навмисному підборі колізій.

Питання 4: Як розподіл Пуассона пояснює вибір порогу перетворення списку бакета на дерево (`TREEIFY_THRESHOLD = 8`)?

Відповідь: При чесній реалізації hashCode() розподіл ключів за кошиками підпорядковується закону Пуассона із середнім значенням $\lambda = 0.5$ (при load factor 0.75). Ймовірність того, що в один кошик випадково потрапить 8 елементів, становить $P(8) \approx 6 \times 10^{-8}$ (шість стомільйонних). Це означає, що при нормальній роботі перетворення на дерево практично ніколи не відбудеться. Поріг 8 обрано так, щоб не витрачати пам’ять на важкі вузли TreeNode у штатному режимі, але захистити систему від деградації при атаках Hash Flooding DoS.

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

❌ «Місткість масиву бакетів може бути довільним парним числом.»
Правильно: Місткість HashMap суворо дорівнює степеню двійки ($2^n$). Якщо вказати 10, JVM округлить місткість до 16.

❌ «При виклику new HashMap(100) мапа вміщує 100 елементів без ресайзу.»
Правильно: 100 буде округлено до 128. Поріг ресайзу становитиме $128 \times 0.75 = 96$. При додаванні 97-го елемента відбудеться ресайз.

❌ «Порожні бакети не витрачають оперативну пам’ять.»
Правильно: Сам масив table алокує безперервний шматок пам’яті під посилання. Масив на 1 000 000 комірок займе ~4 МБ, навіть будучи абсолютно порожнім.