Що таке capacity в HashMap

Типова плутанина на технічних інтерв'ю:

🟢 Junior Level

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

Capacity (місткість) — це фізичний розмір внутрішнього масиву бакетів (table.length) у HashMap, тобто загальна кількість доступних комірок (слотів) для збереження записів або початків зв’язних списків та червоно-чорних дерев.

Місткість за замовчуванням (DEFAULT_INITIAL_CAPACITY): 16 комірок.
Правило степеня двійки: Місткість HashMap завжди суворо дорівнює степеню двійки ($2^n$): 1, 2, 4, 8, 16, 32, 64, 128 тощо.
Максимальна місткість (MAXIMUM_CAPACITY): $2^{30} = 1\,073\,741\,824$.

Приклад завдання місткості в коді

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

public class CapacityDemo {
    public static void main(String[] args) {
        // 1. За замовчуванням: capacity = 16 (масив створиться ліниво при першому put)
        Map<String, Integer> defaultMap = new HashMap<>();

        // 2. Явна вказівка початкової місткості:
        // Передаємо 30 -> HashMap автоматично округлить до найближчого степеня двійки (32)
        Map<String, Integer> customMap = new HashMap<>(30);

        customMap.put("alpha", 1);
    }
}

[!NOTE] Аналогія: Capacity — це кількість абонентських скриньок у поштовому відділенні. Навіть якщо листів надійшло лише два (size = 2), самих скриньок для сортування підготовлено 16 (capacity = 16). Що більше скриньок, то нижча ймовірність, що два різні листи випадково потраплять в одну комірку.

🟡 Middle Level

Різниця між `size` та `capacity`

Типова плутанина на технічних інтерв’ю:

size: Фактична кількість пар «ключ-значення», що зберігаються в HashMap у поточний момент. Повертається публічним методом map.size().
capacity: Фізичний розмір масиву бакетів table.length. Публічного методу map.capacity() у стандартному Java API немає (це внутрішня деталь реалізації).

Чому `capacity` завжди зобов’язаний бути степенем двійки?

В основі блискавичної швидкодії HashMap лежить операція визначення номера бакета за числовим гешем ключа.

Математично для зведення 32-бітного гешу до діапазону $[0, \text{capacity} - 1]$ потрібна операція взяття залишку від ділення: $\text{index} = \text{hash} \pmod{\text{capacity}}$

Проте операція ділення цілих чисел (idiv) на рівні асемблера процесора займає від 15 до 40 тактів. Якщо ж число $N$ є степенем двійки ($N = 2^k$), залишок від ділення математично тотожний порозрядному побітовому «І» з бітовою маскою $(N - 1)$: $\text{index} = (n - 1) \ \& \ \text{hash}$

Побітова операція & виконується процесором за 1 машинний такт.

Що станеться, якщо `capacity` не буде степенем двійки?

Розглянемо випадок $n = 15$ (не степінь двійки): $n - 1 = 14_{10} = 00001110_2$ Молодший біт маски дорівнює 0. При логічному множенні & молодший біт результату завжди буде дорівнювати 0. Це означає, що елементи зможуть потрапляти виключно в парні бакети (0, 2, 4, 6, 8, 10, 12), а всі непарні кошики (1, 3, 5, 7…) назавжди залишаться порожніми! Рівно половина таблиці буде заблокована, а кількість колізій подвоїться.

🔴 Senior Level

Алгоритм округлення: магія методу `tableSizeFor()`

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

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Покроковий розбір роботи алгоритму:

Навіщо cap - 1? Якщо передане число вже є степенем двійки (наприклад, 16), то без віднімання одиниці алгоритм зсунув би його до наступного степеня (32).
Каскадні зсуви >>> та побітове |:
- Після знаходження найстаршого одиничного біта операція n |= n >>> 1 копіює одиницю на сусідній біт праворуч (маємо 2 поспіль одиниці).
- n |= n >>> 2 копіює ці 2 одиниці ще на 2 позиції праворуч (уже 4 одиниці поспіль).
- Зсуви на 4, 8 та 16 гарантують, що всі біти праворуч від старшого заповнюються одиницями (для 32-бітного int).
- Наприклад, для cap = 10: $n = 9$ (00001001_b). У результаті каскаду отримуємо 00001111_b ($15_{10}$).
Додавання 1 (n + 1): Перетворює ланцюжок одиниць 00001111 ($15$) на чистий найближчий степінь двійки 00010000 ($16$).

Ліниве виділення пам’яті (Lazy Allocation)

До моменту вставки першого елемента масив Node<K,V>[] table фізично не існує в пам’яті купи (table == null).

Конструктор new HashMap<>(initialCapacity, loadFactor) лише записує обчислену початкову місткість у службове поле threshold:
```
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
```
Виділення пам’яті під масив table відбувається лише під час першого виклику put() усередині методу resize(). Це зберігає мегабайти оперативної пам’яті в мікросервісах із тисячами порожніх колекцій.

Обмеження `MAXIMUM_CAPACITY` ($2^{30}$)

Чому максимальна місткість дорівнює $1 \ll 30$ ($1\,073\,741\,824$), а не $2^{31}$?
У Java примітив int є знаковим 32-бітним числом у діапазоні від $-2^{31}$ до $2^{31} - 1$.
Якби ми виконали зсув одиниці на 31 біт ліворуч (1 << 31), отримали б від’ємне число Integer.MIN_VALUE ($-2\,147\,483\,648$). Ступінь $2^{30}$ — це максимально можливий додатний степінь двійки, що вміщується у знаковий int.

Memory Footprint масиву бакетів

Сам масив table зберігає виключно посилання на вузли Node<K,V>.
При увімкненому механізмі стиснення вказівників HotSpot (-XX:+UseCompressedOops, активний за замовчуванням для Heap < 32GB):

Заголовок масиву: 16 байтів (Mark Word 8B + Klass Word 4B + Array Length 4B).
Кожна комірка (посилання на Node): 4 байти.
Вирівнювання в пам’яті (padding): до кратності 8 байтів.

Capacity	Розмір масиву посилань у купі (Compressed OOPs)	Без стиснення (`-XX:-UseCompressedOops`)
16 (default)	$16 + (16 \times 4) = 80 \implies 80$ байтів	$24 + (16 \times 8) = 152 \implies 152$ байти
1 024	$16 + (1024 \times 4) = 4112 \implies 4.02$ КБ	$24 + (1024 \times 8) = 8216 \implies 8.02$ КБ
1 048 576 ($2^{20}$)	$16 + (1048576 \times 4) \approx 4$ МБ	$24 + (1048576 \times 8) \approx 8$ МБ

Якщо алокувати new HashMap<>(10_000_000), масив бакетів миттєво забере ~64 МБ оперативної пам’яті ще до збереження реальних бізнес-даних.

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

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

Capacity — це розмір внутрішнього масиву бакетів table.length у HashMap (за замовчуванням 16, максимум $2^{30}$). На відміну від size (кількості доданих пар ключ-значення), capacity завжди є степенем двійки ($2^n$), що дозволяє замінити дороге ділення по модулю надшвидкою побітовою операцією (capacity - 1) & hash за 1 машинний такт. Будь-яке передане в конструктор число автоматично округлюється вгору алгоритмом tableSizeFor(), а сам масив алокується ліниво під час першого виклику put().

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

Питання 1: Що станеться, якщо в конструктор передати `new HashMap<>(0)`? Яким буде `capacity`?

Відповідь: Код виконається успішно без виключень:

Перевірка initialCapacity < 0 пройде успішно (0 допустимий).
Виклик tableSizeFor(0):
- int n = 0 - 1 = -1
- Умова (n < 0) ? 1 : ... поверне 1.
- У поле threshold запишеться значення 1.
При першому put() метод resize() створить масив table місткістю capacity = 1.
Поріг threshold стане рівним (int)(1 * 0.75f) = 0.
При вставці першого ж елемента перевірка if (++size > threshold) (1 > 0) поверне true, і HashMap негайно запустить повторний resize(), подвоївши місткість до 2.

Питання 2: Чи можна отримати поточний `capacity` у наявної `HashMap` без рефлексії?

Відповідь: У стандартному публічному API java.util.HashMap методу capacity() немає.
Його можна визначити непрямими методами:

Якщо відомий початковий розмір і кількість виконаних операцій resize().
Через механізм серіалізації: при виклику writeObject мапа записує свій capacity у потік ObjectOutputStream інструкцією s.writeInt(table.length).

За допомогою Reflection API, зчитавши довжину приватного масиву table.length:

Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
int capacity = (table == null) ? 0 : table.length;

Питання 3: Чому застаріла `Hashtable` не вимагає степеня двійки для `capacity`, а `HashMap` вимагає?

Відповідь:

У Hashtable для розрахунку індексу використовується класичний залишок від ділення:
```
int index = (hash & 0x7FFFFFFF) % tab.length;
```
За замовчуванням початкова місткість Hashtable дорівнює 11 (просте число), а при ресайзі місткість збільшується за формулою (oldCapacity << 1) + 1. Прості непарні числа зменшують колізії при неідеальній хеш-функції.
У HashMap розробники свідомо обрали інший компроміс: пожертвували довільними розмірами заради екстремальної швидкості обчислення індексу через бітову маску (n - 1) & hash за 1 такт. А проблему колізій через степінь двійки вирішили якісною функцією змішування бітів (Perturbation function: (h = key.hashCode()) ^ (h >>> 16)).

Питання 4: Що станеться при спробі додавання елементів у `HashMap`, якщо вона вже досягла `MAXIMUM_CAPACITY` ($2^{30}$)?

Відповідь: Помилки OutOfMemoryError (якщо вистачає купи під вузли) або аварійного завершення не станеться. У методі resize() передбачено захисний блок:

if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

Таблиця припиняє розширювати масив бакетів. Поріг виставляється в Integer.MAX_VALUE ($2^{31} - 1$). Усі наступні елементи накопичуються в уже наявних бакетах, подовжуючи зв’язні списки та червоно-чорні дерева. Часова складність операцій деградує до $O(\log N)$ для дерев’яних бакетів та до $O(N)$ для бакетів без дерев.

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

❌ «capacity повертається методом map.size().»
Правильно: size() повертає кількість записів у мапі, тоді як capacity — це розмір внутрішнього масиву бакетів.

❌ «new HashMap<>(10) створить таблицю на 10 бакетів.»
Правильно: Значення автоматично округлиться вгору до найближчого степеня двійки (16).

❌ «Масив бакетів алокується в пам’яті в момент виклику конструктора.»
Правильно: Алокація пам’яті під масив table відбувається ліниво під час першого виклику put().

🟢 Junior Level

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

Приклад завдання місткості в коді

🟡 Middle Level

Різниця між size та capacity

Чому capacity завжди зобов’язаний бути степенем двійки?

Що станеться, якщо capacity не буде степенем двійки?