🟢 Junior Level

Rehashing (resize) — это процесс увеличения внутреннего массива HashMap. Он происходит в трёх случаях:

1. Первый put() — при создании HashMap массив пуст, первый put его создаёт
2. Превышение порога — когда количество элементов > capacity * loadFactor
3. Treeification при малой таблице — 8 элементов в бакете и capacity < 64

Пример:

HashMap<String, Integer> map = new HashMap<>(); // table = null
map.put("key1", 1);  // Первый put: создаётся массив на 16 бакетов
// ... добавляем ещё 11 элементов (всего 12)
map.put("key13", 13); // 13-й элемент: capacity увеличивается до 32

Почему это важно? Resize — медленная операция O(n). Лучше заранее задать нужный размер.

🟡 Middle Level

Триггеры Resize

Триггер	Условие	Действие
Первый put	table == null	Создаётся массив size 16
Превышение порога	++size > threshold	Удвоение массива
Treeification	8 элементов в бакете, capacity < 64	Resize вместо дерева

Формула порога

threshold = capacity * loadFactor;
// По умолчанию: 16 * 0.75 = 12

Что происходит во время resize?

1. Создаётся новый массив в 2 раза больше
2. Все элементы переносятся в новый массив
3. Пересчитывается threshold

Производительность:

• Время: O(n) — проходит по всем элементам
• Память: временно существует два массива
• GC pressure: создаёт нагрузку на сборщик мусора

Как избежать resize?

// Если знаете, что будет 1000 элементов:
int capacity = (int)(1000 / 0.75f) + 1;
new HashMap<>(capacity);

Типичные ошибки

1. Не учитывать округление — new HashMap(1000) даст capacity 1024, threshold 768
2. Ресайз в hot path — в цикле с частыми put resize вызывает latency spikes
3. Многопоточный resize — в Java 7 приводил к зацикливанию

Когда resize допустим

Resize допустим: при начальной загрузке данных (одноразово), для некритичных по latency операций. НЕ допустим: в hot path обработчика HTTP-запроса, в real-time системах.

🔴 Senior Level

Lazy Initialization

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // Первый resize!
    ...
}

Первый resize происходит при первом put() — это создаёт начальный массив.

Resize при Treeification

Кроме resize, при 8 элементах в бакете и capacity < 64 происходит resize ВМЕСТО treeification — это попытка разнести элементы по новым бакетам, а не превращать список в дерево.

Multi-threaded Resize Danger

HashMap не потокобезопасна:

• Java 7: Параллельный resize → циклические ссылки → infinite loop
• Java 8+: Исправлено через tail insertion, но потеря данных возможна

// Поток A и B одновременно делают resize:
// Оба создают новый массив, переносят элементы
// Результат: потеря элементов, undefined behavior

Performance Impact

Resize — одна из самых дорогих операций HashMap:

• Аллокация нового массива: O(capacity)
• Копирование элементов: O(size)
• Общее: O(n)

В latency-sensitive системах это вызывает spike от долей миллисекунды (для маленьких Map) до 100+ мс (для Map с миллионами элементов; зависит от JVM и размера HashMap).

Production Monitoring

Признаки проблем с resize:

• Периодические задержки (spikes) в метриках latency
• Рост GC activity в моменты resize
• Memory profiling: одновременное существование двух массивов

Best Practices

// Guava:
Map<K, V> map = Maps.newHashMapWithExpectedSize(expectedSize);

// Или вручную:
new HashMap<>((int)(expectedSize / 0.75f) + 1);

---

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

Обязательно знать:

• Три триггера: первый put (создание массива), ++size > threshold, treeification при capacity < 64
• threshold = capacity * loadFactor; по умолчанию 16 * 0.75 = 12
• Resize = O(n): аллокация нового массива + копирование элементов
• Lazy Initialization: массив создаётся при первом put, не в конструкторе (Java 8+)
• Java 7: параллельный resize → infinite loop; Java 8+: исправлено, но потеря данных возможна
• Resize в hot path — причина latency spikes

Частые уточняющие вопросы:

• Почему resize удваивает, а не +16? — удвоение даёт амортизированную O(1) вставку
• Можно ли избежать resize? — да, задать initialCapacity = (expected / 0.75) + 1
• Почему treeification вызывает resize? — попытка разнести элементы вместо дерева
• Resize допустим? — при начальной загрузке да; в hot path HTTP-обработчика — нет

Красные флаги (НЕ говорить):

• «Resize происходит при каждом put» — нет, только при превышении threshold
• «Java 8 полностью безопасна при resize» — нет, потеря данных всё ещё возможна
• «Resize пересчитывает hashCode» — нет, проверяется один бит (hash & oldCap)

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

• [[16. Что такое load factor в HashMap]]
• [[17. Что такое capacity в HashMap]]
• [[19. Что происходит при rehashing]]
• [[22. Как работает HashMap в многопоточной среде]]