🔑 Раздел 10 · Вопрос #28

Как правильно выбрать начальный capacity для HashMap

Если конструктор вызывается без параметров (new HashMap<>()), по умолчанию выбирается ёмкость 16 с порогом расширения 12 ($16 \times 0.75$). Если заранее известно, что в карту б...

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 Junior Level

Начальный capacity (Initial Capacity) — это размер внутреннего массива бакетов, который резервируется в памяти при создании HashMap.

Если конструктор вызывается без параметров (new HashMap<>()), по умолчанию выбирается ёмкость 16 с порогом расширения 12 ($16 \times 0.75$). Если заранее известно, что в карту будет добавлено, например, 1 000 элементов, создание HashMap по умолчанию приведет к 7 последовательным ресайзам ($16 \to 32 \to 64 \to 128 \to 256 \to 512 \to 1024 \to 2048$), каждый из которых требует выделения нового массива и копирования всех существующих элементов.

Золотое правило расчета

Чтобы добавить $N$ элементов без единого ресайза, начальную ёмкость вычисляют с учетом коэффициента загрузки loadFactor (по умолчанию $0.75$):

\[\text{capacity} = \left\lceil \frac{\text{ожидаемое количество}}{0.75} \right\rceil = \text{ожидаемое количество} \times \frac{4}{3}\] 
import java.util.HashMap;
import java.util.Map;

public class InitialCapacityDemo {
    public static void main(String[] args) {
        int expectedSize = 100;

        // Расчет вручную: 100 / 0.75 = 133.33 -> округляем вверх до 134
        int capacity = (int) Math.ceil(expectedSize / 0.75f);
        Map<String, Integer> map = new HashMap<>(capacity);

        // Начиная с Java 19 — современный официальный способ:
        Map<String, Integer> modernMap = HashMap.newHashMap(expectedSize);
    }
}

Аналогия: Если вы ждете на банкет 100 гостей, вы не заказываете сначала столик на 16 мест, а потом 7 раз подряд не меняете зал на всё больший и больший по мере прибытия гостей. Вы сразу бронируете зал на 134+ мест, чтобы всем хватило пространства с комфортом.

🟡 Middle Level

Почему наивный вызов new HashMap<>(1000) приводит к ресайзу?

Частая ошибка на собеседованиях — считать, что вызов new HashMap<>(1000) предотвратит ресайз для 1000 элементов:

  1. Вы передали 1000. Метод tableSizeFor(1000) округляет это число до ближайшей степени двойки вверх $\to$ 1024.
  2. Порог расширения рассчитывается как: \(\text{threshold} = 1024 \times 0.75 = 768\)
  3. Вы начинаете наполнять карту элементами.
  4. При добавлении 769-го элемента условие ++size > threshold ($769 > 768$) становится истинным!
  5. Происходит дорогостоящий ресайз таблицы с 1024 до 2048 бакетов.

Правильный расчет для 1000 элементов:

\(\text{initialCapacity} = (int) \left(\frac{1000}{0.75f}\right) + 1 = 1334\)

  • tableSizeFor(1334) округляет вверх до степени двойки $\to$ 2048.
  • Порог: $\text{threshold} = 2048 \times 0.75 = 1536$.
  • Все 1000 элементов гарантированно помещаются в таблицу без ресайза ($1000 \le 1536$).

Официальный API: фабричные методы Java 19+

Начиная с Java 19 (JDK 19, JEP), разработчикам больше не нужно вручную производить деление на 0.75f. В стандартную библиотеку были добавлены статические фабричные методы:

// Создает HashMap с емкостью, достаточной для 10 000 элементов без ресайза:
Map<String, Order> orders = HashMap.newHashMap(10_000);

// Аналогично для связанных карт и множеств:
Map<String, Order> linkedOrders = LinkedHashMap.newLinkedHashMap(10_000);
Set<String> uniqueTags = HashSet.newHashSet(10_000);

Внутри OpenJDK метод HashMap.newHashMap реализован именно через формулу деления:

static int calculateHashMapCapacity(int numMappings) {
    return (int) Math.ceil(numMappings / (double) DEFAULT_LOAD_FACTOR);
}

🔴 Senior Level

Влияние завышенной ёмкости на производительность (Over-allocation Overhead)

Существует соблазн всегда задавать емкость «с огромным запасом» (например, new HashMap<>(1_000_000) под 100 элементов). Это порождает серьезные негативные последствия:

  1. Расход Heap Memory: Массив ссылок table на 1 000 000 ячеек при включенном UseCompressedOops мгновенно аллоцирует 4 МБ памяти под пустые ссылки null (или 8 МБ без сжатия указателей) еще до вставки данных.
  2. Деградация скорости итерации: Сложность обхода map.keySet(), map.values() и map.entrySet() составляет $O(\text{capacity} + \text{size})$. Итератор вынужден последовательно перебирать весь массив table.length. При capacity = 1_000_000 и size = 10 итератор выполнит 999 990 пустых проверок ячеек памяти на null, что вызовет тысячи аппаратных промахов кэша CPU (L1/L2/L3 Cache Misses).
  3. Нагрузка на сборщик мусора (GC Pressure): Крупные массивы ссылок требуют от GC сканирования корзины Card Table при отслеживании межрегиональных указателей (G1 / ZGC), что увеличивает время пауз на фазах разметки.

Сравнение подходов к созданию HashMap

Подход Ресайзы при $N=1000$ Итоговый Capacity Память массива ссылок Скорость вставки
new HashMap<>() (default) 7 ресайзов 2048 8 КБ Медленно (латентные всплески)
new HashMap<>(1000) (ошибочный) 1 ресайз (на 769-м) 2048 8 КБ Средне (один латентный спайк)
HashMap.newHashMap(1000) 0 ресайзов 2048 8 КБ Максимальная (стабильный latency)
new HashMap<>(100_000) (избыточный) 0 ресайзов 131 072 512 КБ Быстрая вставка / ужасная итерация

4 Tricky Questions

1. Что произойдет, если создать new HashMap<>(12) и добавить ровно 12 элементов? Сработает ли resize()?

Ответ: Да, сработает! Проследим логику HotSpot:

  1. Вы передали 12. Метод tableSizeFor(12) округляет 12 вверх до ближайшей степени двойки $\to$ 16.
  2. Порог расширения рассчитывается как: \(\text{threshold} = 16 \times 0.75 = 12\)
  3. Вставляем 11 элементов: size становится 11 ($11 \le 12$).
  4. Вставляем 12-й элемент: putVal выполняет проверку: if (++size > threshold) resize(); Подставляем значения: 12 > 12 $\implies$ false. Ресайза пока нет!
  5. Но если мы добавим 13-й элемент: $13 > 12 \implies$ сработает resize(). Если же требовалось сохранить ровно 12 элементов с гарантией отсутствия ресайза, new HashMap<>(12) выдерживает ровно 12 элементов на грани фола. Но при 13 элементах таблица расширится.

2. Почему в старых библиотеках (Guava) формула выглядела как (int)(expected / 0.75f + 1.0f), а не просто (int)(expected / 0.75f)?

Ответ: Причина кроется в особенностях арифметики чисел с плавающей точкой (float) и операции приведения к целому числу ((int)):

  • В Java приведение (int) floatValue отбрасывает дробную часть (производит округление вниз, floor).
  • Например, для expected = 3: $3 / 0.75 = 4.0$. Однако из-за погрешностей представления float результат деления может оказаться 3.9999998f.
  • Приведение (int) 3.9999998f даст 3! В результате tableSizeFor(3) вернет 4, threshold = 4 * 0.75 = 3. При вставке 3-го элемента или 4-го произойдет ресайз. Добавление + 1.0f или использование Math.ceil() гарантирует защиту от неточного округления чисел с плавающей точкой.

3. Имеет ли смысл задавать initialCapacity для коллекций, в которых гарантированно будет храниться не более 3–5 элементов?

Ответ: Обычно нет. Дефолтный размер 16 ячеек вмещает до 12 элементов ($16 \times 0.75$) без единого ресайза. Массив на 16 ссылок занимает всего около 80 байт в оперативной памяти. Вычисление кастомного capacity ради экономии 40 байт создает ненужное усложнение кода без измеримого выигрыша. Задавать initialCapacity имеет смысл, когда ожидаемый размер коллекции превышает стандартный порог в 12 элементов (десятки, сотни или тысячи записей).

4. Как правильно задать начальную емкость, если одновременно меняется loadFactor (например, передан 0.5f)?

Ответ: Формула остается универсальной: \(\text{capacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil\) Если ожидается 100 элементов, а loadFactor = 0.5f: \(\text{capacity} = \left\lceil \frac{100}{0.5f} \right\rceil = 200\) В конструктор передается:

Map<Key, Value> map = new HashMap<>(200, 0.5f);

tableSizeFor(200) округлит емкость до 256. Порог threshold станет $256 \times 0.5 = 128$, что позволит гарантированно вместить 100 элементов без расширения массива.

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

  • Формула расчета емкости: $\text{initialCapacity} = \lceil \text{expectedSize} / 0.75 \rceil$.
  • Ошибка new HashMap<>(1000): Округляется до 1024, порог становится 768. Ресайз произойдет на 769-м элементе!
  • Правильное значение для 1000: capacity = 1334 (округлится до 2048, порог 1536 $\implies$ без ресайзов).
  • Современный стандарт (Java 19+): Используйте HashMap.newHashMap(expectedSize) или HashSet.newHashSet(expectedSize).
  • Опасность завышения: Избыточный capacity приводит к потере памяти и резкому замедлению итерации ($O(\text{capacity} + N)$).
  • Маленькие коллекции: При размере до 12 элементов дефолтного конструктора new HashMap<>() более чем достаточно.

Связанные темы