🟢 Junior Level

Capacity (ємність) — це кількість комірок (бакетів) у внутрішньому масиві HashMap.

• Початкове значення: 16 (за замовчуванням)
• Завжди степінь двійки: 16, 32, 64, 128, 256…

Приклад:

HashMap<String, Integer> map = new HashMap<>();
// capacity = 16 (за замовчуванням)
// При 12 елементах (16 * 0.75) — збільшиться до 32

HashMap<String, Integer> map2 = new HashMap<>(64);
// capacity = 64 з самого початку

Проста аналогія: Capacity — це кількість поштових ящиків у під’їзді. Чим більше ящиків, тим менший шанс, що два листи потраплять в один.

🟡 Middle Level

Властивості Capacity

Параметр	Значення	Опис
Default	16	Початковий розмір
Minimum	1	Мінімально можливий
Maximum	2^30	Максимум (1,073,741,824)
Крок	x2	Збільшується вдвічі

Чому завжди степінь двійки?

Це потрібно для швидкої формули:

index = (n - 1) & hash;  // Працює лише при n = 2^k

Якби n було 15 (не степінь двійки):

n-1 = 14 => 0000 1110

Молодший біт завжди 0 — всі непарні бакети порожні. Це катастрофічні колізії.

Округлення Initial Capacity

new HashMap(10)  // capacity стане 16
new HashMap(33)  // capacity стане 64
new HashMap(100) // capacity стане 128

Метод tableSizeFor() знаходить найближчий степінь двійки вгору.

Зв’язок з Threshold

threshold = capacity * loadFactor

При capacity=16, loadFactor=0.75: threshold = 12. При 13-му елементі — resize.

Вплив на продуктивність

Занадто маленька: Часті resize (O(n)), затримки Занадто велика: Ітерація повільна (прохід по порожніх бакетах). Великий capacity виправданий: (1) коли ви знаєте очікувану кількість елементів і хочете уникнути resize; (2) коли Map живе довго і часто читається. НЕ виправданий: для тимчасових/маленьких Map.

🔴 Senior Level

Internal Implementation

transient Node<K,V>[] table; // Сам масив

При створенні new HashMap() масив дорівнює null. Ініціалізація — лінива, при першому put().

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;
}

Цей бітовий трюк заповнює всі біти справа від старшого одиничного біта, потім додає 1.

Resize Optimization

При подвоєнні capacity (Java 8+):

// Елемент або залишається на місці, або зміщується на oldIndex + oldCap
if ((e.hash & oldCap) == 0) {
    // Той самий індекс
} else {
    // Індекс + oldCapacity
}

Не потрібно перераховувати хеші — перевіряється один біт.

Memory Implications

• capacity=16: масив ~128 байт (16 посилань × 8 байт)
• capacity=1,000,000: масив ~4-8MB (навіть при 0 елементів!). Посилання на 64-bit JVM без стиснення вказівників: 1M × 8 байт ≈ 8MB. При UseCompressedOops (за замовчуванням, стискає посилання до 4 байт): 1M × 4 байти ≈ 4MB.
• При iteration: O(capacity + size) — порожні бакети теж обходяться

Edge Cases

1. capacity = MAXIMUM_CAPACITY (2^30): Більше не збільшується
2. capacity > MAXIMUM_CAPACITY: Помилка (threshold = Integer.MAX_VALUE)
3. Initial capacity = 0: Допустимо, перший put створить capacity = 1

Production Best Practices

// Для 1000 елементів:
int expected = 1000;
int capacity = (int)(expected / 0.75f) + 1; // 1334
// HashMap округлить до 2048
new HashMap<>(capacity);

Це запобігає resize і забезпечує стабільну latency.

---

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

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

• Capacity = кількість бакетів, завжди степінь двійки (16, 32, 64…)
• Default = 16, Maximum = 2^30, подвоюється при resize
• new HashMap(10) → capacity = 16 (округлення вгору до степеня двійки через tableSizeFor)
• Формула індексу: (n-1) & hash працює ЛИШЕ при n = 2^k
• Лінива ініціалізація: масив створюється при першому put (Java 8+)
• tableSizeFor() — бітовий алгоритм: заповнює всі біти справа від старшого + 1
• При iteration: O(capacity + size) — порожні бакети теж обходяться

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

• Що буде при capacity = 0? — допустимо, перший put створить capacity = 1
• Чому не прості числа? — для (n-1) & hash потрібен степінь двійки; Hashtable використовує прості числа з %
• Як tableSizeFor знаходить степінь двійки? — через серії n |= n >>> k (1,2,4,8,16 біт)
• Скільки пам’яті при capacity = 1M? — ~4-8MB (масив посилань, залежить від UseCompressedOops)

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

• «Capacity може бути будь-яким числом» — ні, завжди степінь двійки
• «HashMap створює масив при конструкторі» — ні, ліниво при першому put
• «capacity = 10 створить 10 бакетів» — ні, округлить до 16

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

• [[16. Що таке load factor в HashMap]]
• [[18. Коли відбувається rehashing в HashMap]]
• [[19. Що відбувається під час rehashing]]
• [[28. Як правильно підібрати початкову capacity для HashMap]]