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