🟢 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 — это unacceptable.

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]]