Что такое capacity в HashMap

Частая путаница на собеседованиях:

🟢 Junior Level

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

Аналогия: 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, 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). В результате каскада получаем 00001111 ($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 МБ оперативной памяти еще до добавления реальных данных.

4 Tricky Questions

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(), можно отследить удвоения.
Если доступна сериализация: при сериализации HashMap записывает свой capacity в поток ObjectOutputStream вызовом s.writeInt(table.length).

С помощью Java Reflection доступ к приватному полю table позволяет прочитать 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 (простое число), а при ресайзе размер увеличивается по формуле newCapacity = (oldCapacity << 1) + 1. Нечетные и простые числа снижают вероятность коллизий при слабом качестве хеш-функции.
В HashMap осознанно применили компромисс: пожертвовали свободой выбора размера ради экстремальной скорости расчета индекса через побитовую маску (n - 1) & hash. А проблему потенциальных коллизий из-за степени двойки решили внедрением высокоэффективной функции перемешивания хеша (Perturbation function: (h = key.hashCode()) ^ (h >>> 16)).

4. Что произойдет при попытке добавления элементов в `HashMap`, если она уже достигла `MAXIMUM_CAPACITY` ($2^{30}$)?

Ответ: Исключения OutOfMemoryError (если хватает Heap под ноды) или сбоя не произойдет. В методе resize() предусмотрена защита:

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

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

🎯 Шпаргалка для интервью

Что такое Capacity: Физический размер массива бакетов table.length. Default = 16, Max = $2^{30}$.
Связь с Size: size — количество элементов в Map, capacity — размер внутреннего массива.
Почему степень двойки ($2^n$): Позволяет заменить медленное деление по модулю % мгновенной побитовой маской (capacity - 1) & hash (1 такт CPU).
Алгоритм tableSizeFor: Каскадный сдвиг битов n |= n >>> 1...16 округляет любое число вверх до ближайшей степени двойки.
Lazy Allocation: Память под массив table выделяется не в конструкторе, а при первом вызове put().
При capacity = 0: Создается массив размера 1, который удваивается при первой же вставке.

🟢 Junior Level

Пример задания ёмкости в коде

🟡 Middle Level

Разница между size и capacity

Почему capacity всегда обязан быть степенью двойки?

Что произойдет, если capacity не будет степенью двойки?

🔴 Senior Level

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