🟢 Junior Level

Початкова capacity — це розмір внутрішнього масиву HashMap, який задається при створенні.

Якщо не вказати — буде 16 за замовчуванням. Але якщо ви знаєте, скільки елементів буде в мапі, краще задати capacity заздалегідь.

Навіщо? Щоб HashMap не витрачала час на збільшення (resize), яке повільне.

Проста формула:

int capacity = (очікувана_кількість / 0.75) + 1;
Map<String, Integer> map = new HashMap<>(capacity);

Приклад:

// Очікуємо 100 елементів:
int capacity = (int) (100 / 0.75) + 1; // = 134
// HashMap округлить до найближчого степеня двійки зверху: 256
Map<String, Integer> map = new HashMap<>(134);
// threshold = 256 * 0.75 = 192 — 100 елементів помістяться без resize

🟡 Middle Level

Проблема ресайзу

Кожен resize — це O(n): створення нового масиву + копіювання всіх елементів.

// Без вказання capacity:
new HashMap<>();       // capacity = 16, threshold = 12
// При 13 елементах: resize до 32
// При 25 елементах: resize до 64
// При 49 елементах: resize до 128
// ... і так далі

Кожен resize — затримка і навантаження на GC.

Формула ідеальної Capacity

initialCapacity = (expectedSize / loadFactor) + 1

Чому +1? Поріг перевіряється як ++size > threshold. Без +1 останній елемент викличе resize.

Округлення до степеня двійки

HashMap завжди округлює capacity вгору до степеня двійки:

Передали	Стало
10	16
100	128
1000	1024
1335	2048

Практичний приклад для 1000 елементів

// Неправильно:
new HashMap<>(1000);
// → capacity = 1024, threshold = 768
// → При 769 елементах resize до 2048!

// Правильно:
new HashMap<>((int)(1000 / 0.75f) + 1); // = 1334
// → capacity = 2048, threshold = 1536
// → 1000 елементів поміщаються без resize

Коли не потрібно вказувати capacity

• Маленькі колекції (2-5 елементів) — overhead розрахунку більший за користь
• Невідома кількість елементів — конструктор за замовчуванням

Guava Helpers

// Google Guava — вже містить правильну формулу:
Map<K, V> map = Maps.newHashMapWithExpectedSize(1000);

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

1. Передати очікувану кількість напряму — new HashMap(1000) дасть threshold 768
2. Забути +1 — останній елемент викличе resize
3. Занадто великий capacity — повільна ітерація по порожніх бакетах

🔴 Senior Level

tableSizeFor Internal

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

Цей бітовий алгоритм знаходить найближчий степінь двійки за O(1).

Resize Cost Analysis

При resize capacity=N:

• Алокація: N посилань × 8 байт
• Копіювання: size елементів
• GC: старий масив → garbage
• Latency spike: 1-100ms залежно від розміру

У latency-sensitive системах (HFT, real-time) resize — це неприйнятно.

Iteration Performance

// capacity = 1,000,000, size = 10
for (var entry : map.entrySet()) { ... }
// Ітератор проходить 1,000,000 бакетів, з яких 10 заповнені
// 999,990 порожніх перевірок — величезний overhead

Не завищуйте capacity без необхідності.

Memory Trade-off

Capacity	Memory (масив)	Ресайзи	Ітерація
Точно під розмір	Мінімум	Часті	Швидка
З запасом (формула)	Трохи більше	Ні	Швидка
Сильно завищений	Багато	Ні	Повільна

Production: Dynamic Sizing

В деяких фреймворках (Netty, Kafka) використовуються custom map з:

• Передбачуваною latency (без resize)
• Ring buffer для eviction
• Open addressing для економії пам’яті

Benchmark: Impact of Wrong Capacity

Сценарій	Час вставки 1M елементів
Без capacity (resize)	120ms
Правильний capacity	45ms
10x завищений	50ms (вставка) / 500ms (ітерація)

Best Practice Formula

/**
 * Створює HashMap без ресайзу для expectedSize елементів.
 */
public static <K, V> HashMap<K, V> newHashMap(int expectedSize) {
    return new HashMap<>((int) Math.ceil(expectedSize / 0.75) + 1);
}

---

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

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

• Формула: initialCapacity = (expectedSize / loadFactor) + 1 — щоб уникнути resize
• HashMap округлює до найближчого степеня двійки через tableSizeFor()
• Без формули: new HashMap(1000) → capacity=1024, threshold=768 → resize при 769 елементах
• З формулою: (1000/0.75)+1=1334 → capacity=2048, threshold=1536 → без resize
• Кожен resize = O(n): алокація + копіювання + GC pressure + latency spike
• Завищений capacity = повільна ітерація по порожніх бакетах (O(capacity + size))
• Не вказувати capacity для маленьких колекцій (2-5 елементів)

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

• Чому +1 у формулі? — поріг перевіряється як ++size > threshold; без +1 останній елемент викличе resize
• Що таке tableSizeFor? — бітовий алгоритм: знаходить найближчий степінь двійки за O(1)
• Коли Guava Maps.newHashMapWithExpectedSize? — вже містить правильну формулу
• Скільки коштує resize? — 1-100ms залежно від розміру; для 1M елементів ~150ns (P99 ~5000ns)

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

• «new HashMap(1000) створить 1000 бакетів» — ні, 1024, і threshold = 768
• «Чим більше capacity тим краще» — ні, ітерація повільніша, пам’ять витрачається
• «Capacity можна змінювати після створення» — ні, задається в конструкторі

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

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