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

Что происходит при rehashing

4. Утилизация старого массива: Ссылка table переключается на новый массив, а старый массив становится доступен для сборщика мусора (GC).

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

🟢 Junior Level

Rehashing (ресайз / перехеширование) — это внутренний процесс HashMap, при котором создается новый массив бакетов в 2 раза большего размера, а все существующие элементы перераспределяются по новым позициям.

Что происходит пошагово:

  1. Создание нового массива: Выделяется массив Node<K,V>[] удвоенной длины ($16 \to 32$, $32 \to 64$ и т.д.).
  2. Перенос элементов: Каждый существующий элемент из старого массива перемещается в новую ячейку. При этом элемент либо остается на своем прежнем индексе, либо сдвигается на позицию старый_индекс + старая_емкость.
  3. Обновление порога (threshold): Порог срабатывания следующего ресайза удваивается.
  4. Утилизация старого массива: Ссылка table переключается на новый массив, а старый массив становится доступен для сборщика мусора (GC).
import java.util.HashMap;
import java.util.Map;

public class RehashingVisualDemo {
    public static void main(String[] args) {
        // Начальная ёмкость = 16, threshold = 12
        Map<Integer, String> map = new HashMap<>();

        for (int i = 1; i <= 12; i++) {
            map.put(i, "Value" + i);
        }

        // Вставка 13-го элемента запускает resize():
        // 1. Выделяется массив на 32 ячейки
        // 2. Все 13 элементов переносятся по новым индексам
        // 3. Новый порог становится 24 (32 * 0.75)
        map.put(13, "TriggerResize");
    }
}

Аналогия: Представьте гардероб, в котором было 16 секций с вешалками. Гардероб расширили до 32 секций. Чтобы не перевешивать все вещи заново, гардеробщик берет вещи из каждой секции и раскладывает их по простому правилу: половину оставляет в текущей секции, а вторую половину переносит ровно на 16 позиций вперед.

🟡 Middle Level

Элегантный битовый трюк: (e.hash & oldCap)

Главное инженерное новшество Java 8+ в процедуре resize() заключается в том, что HashMap вообще не пересчитывает хеши и даже не вычисляет заново полный индекс через операцию (newCap - 1) & hash.

Поскольку емкость таблицы всегда является степенью двойки ($2^k$), при удвоении емкости в битовой маске добавляется ровно один старший бит (соответствующий весу oldCap):

Старая емкость (16):   oldCap = 00010000_2
Старая маска (15):     n - 1  = 00001111_2
Новая емкость (32):    newCap = 00100000_2
Новая маска (31):      n - 1  = 00011111_2
                                ^
                      Тот самый новый бит!

Судьба элемента зависит исключительно от значения этого единственного бита в e.hash:

if ((e.hash & oldCap) == 0) {
    // Новый бит равен 0 -> индекс НЕ МЕНЯЕТСЯ (остается oldIndex)
} else {
    // Новый бит равен 1 -> индекс становится (oldIndex + oldCap)
}

Разделение цепочки: формирование Lo- и Hi-списков

При обходе связного списка в бакете HashMap за один линейный проход формирует две независимые цепочки с сохранением исходного порядка элементов (Tail Insertion):

Node<K,V> loHead = null, loTail = null; // Список для старого индекса
Node<K,V> hiHead = null, hiTail = null; // Список для индекса (index + oldCap)
Node<K,V> next;

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead; // Поместили в старый индекс
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; // Поместили в новый индекс со смещением
}
  • Tail Insertion: Добавление новых элементов в хвост списков сохраняет относительный порядок узлов. В Java 7 использовался Head Insertion (добавление в голову), из-за чего при конкурентном доступе цепочка разворачивалась в обратную сторону и образовывалось фатальное кольцо ссылок (бесконечный цикл и 100% CPU).

🔴 Senior Level

Механизм TreeNode.split(): расщепление красно-чёрного дерева

Если в бакете уже сформировано красно-чёрное дерево (e instanceof TreeNode), вызов делегируется методу split(this, newTab, j, oldCap).

Узел TreeNode обладает двойственной природой: он одновременно является узлом красно-чёрного дерева (left, right, parent) и элементом двусвязного списка (prev, next).

При разделении дерева:

  1. Метод split() проходит по связям next двусвязного списка узлов, аналогично обычному списку формируя две группы узлов: loHead и hiHead, попутно подсчитывая их количество (lc и hc).
  2. Де-трификация (Untreeification): Если количество элементов в образовавшейся подгруппе $\le \text{UNTREEIFY_THRESHOLD}$ (6 элементов), дерево деградирует обратно в простой односвязный список Node: 
    if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = loHead.untreeify(map);
else {
    tab[index] = loHead;
    if (hiHead != null)
        loHead.treeify(tab); // Полная ребалансировка красно-чёрного дерева
}
  3. Если же в ветке осталось 7 или более элементов, заново вызывается treeify(tab) для построения сбалансированного красно-чёрного дерева с пересчетом цветов и поворотов.

Нагрузка на оперативную память и сборщик мусора (GC Pressure)

Во время выполнения resize():

  • Пиковое потребление памяти под массивы: В памяти одновременно находятся оба массива (oldTab и newTab).
    • При capacity = 2 миллиона: oldTab занимает $\approx 8$ МБ ссылок (при Compressed OOPs), newTab на 4 миллиона занимает $\approx 16$ МБ. Итого кратковременно расходуется 24 МБ под таблицы ссылок.
  • Write Barriers: Массовое переписывание ссылок в массиве вызывает срабатывание механизмов Write Barrier сборщика мусора (G1, ZGC), фиксирующих изменения ссылочных полей в Card Table / Remembered Sets.
  • Старый массив: Становится недостижимым мусором сразу после завершения метода resize(). Если таблица была долгоживущей и находилась в Old Generation, освобождение старого массива потребует запуска Concurrent Mark / Mixed GC в G1.

4 Tricky Questions

1. Почему при рехешировании в Java 8+ метод key.hashCode() никогда не вызывается повторно?

Ответ: В каждом узле Node<K,V> 32-битный хеш ключа (hash) вычисляется ровно один раз при вызове put() и сохраняется в финальное поле final int hash;. При ресайзе HashMap читает уже сохраненное поле e.hash и проверяет один бит через (e.hash & oldCap) == 0. Это исключает любые повторные затраты на вычисление хеш-кода объектов (что критично, например, для тяжелых строковых ключей или составных доменных объектов).

2. Почему порог де-трификации (UNTREEIFY_THRESHOLD = 6) не равен порогу трификации (TREEIFY_THRESHOLD = 8)?

Ответ: Разница в 2 единицы (порог 8 для дерева и 6 для возврата в список) — это классический инженерный прием предотвращения флаппинга (гистерезис / flapping / thrashing).

Если бы оба порога были равны (например, 8):

  • Добавление 8-го элемента превращало бы список в дерево.
  • Последующее удаление одного элемента (size = 7) тут же запускало бы обратную конвертацию дерева в список.
  • Следующий put() снова строил бы дерево. Постоянная конвертация «список $\leftrightarrow$ дерево» под нагрузкой привела бы к катастрофическому падению производительности и взрывному расходу памяти. Зазор между 6 и 8 сглаживает граничные колебания.

3. Что произойдет, если поток А читает данные через map.get("key"), пока поток B выполняет resize()?

Ответ: HashMap не является потокобезопасной. При гонке потоков между чтением и ресайзом возможны следующие аномалии:

  1. Чтение вернет null для реально существующего ключа: Метод resize() присваивает новый массив ссылке table = newTab в самом начале метода. Если поток A обратится к table до того, как поток B успеет перенести туда искомый бакет, поток A прочитает null в ячейке и решит, что ключа в Map нет.
  2. ConcurrentModificationException при итерации: Счётчик структурных модификаций modCount не защищен барьерами памяти, что приведет к немедленному сбою итератора.
  3. Потеря видимости: Отсутствие инструкций volatile и барьеров памяти (Memory Barriers) допускает чтение устаревших ссылок next из кэшей ядер CPU.

4. Может ли размер таблицы при ресайзе превысить максимальное значение MAXIMUM_CAPACITY ($2^{30}$)? Что происходит при попытке переполнения?

Ответ: Нет, емкость никогда не превысит $2^{30}$ ($1\,073\,741\,824$). В коде метода resize() стоит явная проверка:

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

Если текущий capacity уже равен $2^{30}$, HashMap отказывается создавать новый массив и оставляет oldTab без изменений. Порог threshold выставляется в максимальное положительное число Integer.MAX_VALUE ($2^{31} - 1$). С этого момента ресайз больше не запустится никогда, а все новые элементы будут принудительно оседать в существующих бакетах, увеличивая длину цепочек и красно-чёрных деревьев.

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

  • Суть Rehashing: Удвоение емкости массива бакетов ($N \to 2N$) и распределение существующих элементов.
  • Битовый фокус: Хеши заново не пересчитываются. Проверяется один бит: (e.hash & oldCap) == 0.
    • Бит равен 0 $\to$ элемент остается на индексе index.
    • Бит равен 1 $\to$ перемещается на index + oldCap.
  • Lo и Hi списки: Цепочки разделяются за один проход с сохранением порядка следования узлов (Tail Insertion).
  • Поведение деревьев (TreeNode.split):
    • Подгруппа $\le 6$ узлов $\to$ де-трификация (untreeify) обратно в связный список.
    • Подгруппа $> 6$ узлов $\to$ ребалансировка красно-чёрного дерева.
  • Гистерезис: Зазор между порогом трификации (8) и де-трификации (6) предотвращает флаппинг при частых добавлениях/удалениях.
  • Потокобезопасность: Ресайз в конкурентной среде приводит к гонкам данных, фантомным null при get() и порче структур данных.

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