Что происходит с бакетом при переполнении в HashMap

Общий механизм обработки коллизий в HashMap

При переполнении бакета (bucket) в HashMap происходит процесс, называемый разрешением коллизий методом цепочек (separate chaining). В Java 8 и выше этот механизм был оптимизирован для повышения производительности.

Исходное состояние бакета

Каждый бакет в HashMap представляет собой цепочку узлов. До Java 8 это был односвязный список элементов Entry<K, V>. Начиная с Java 8, при достижении определенного порога цепочка преобразуется в сбалансированное бинарное дерево (точнее, красно-черное дерево).

// Пример узла в Java 8+ (упрощённо)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Ссылка на следующий узел в цепочке
}

Процесс при переполнении

1. Добавление элемента в цепочку:

   • При коллизии (совпадении хэш-кодов) новый элемент добавляется в начало цепочки соответствующего бакета (время O(1)).
   • При этом next нового узла указывает на старую голову цепочки.

2. Преобразование списка в дерево (Java 8+):

   • Когда длина цепочки достигает порога TREEIFY_THRESHOLD (по умолчанию 8), и общее количество бакетов превышает MIN_TREEIFY_CAPACITY (по умолчанию 64), цепочка преобразуется в красно-черное дерево.
   • Это улучшает производительность поиска с O(n) до O(log n) для длинных цепочек.

// Условная логика преобразования в дерево
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

1. Обратное преобразование (дерево → список):
   • Если размер дерева уменьшается ниже UNTREEIFY_THRESHOLD (по умолчанию 6), оно снова преобразуется в односвязный список для экономии памяти.

Влияние на производительность

• До Java 8: длинные цепочки могли деградировать до O(n) для операций get() и put().
• Java 8+: дерево обеспечивает O(log n) даже для некачественных хэш-функций, что защищает от атак на хэш-таблицу.

Пример сценария переполнения

Допустим, у нас есть HashMap с плохой хэш-функцией, возвращающей одинаковый индекс для всех ключей:

HashMap<Key, String> map = new HashMap<>();
// Все ключи попадают в один бакет
for (int i = 0; i < 10; i++) {
    map.put(new BadKey(i), "Value" + i);
}
// При добавлении 9-го элемента (индекс 8) цепочка преобразуется в дерево

Критические моменты

• Рехеширование (resize): При достижении loadFactor (по умолчанию 0.75) происходит увеличение размера массива бакетов в 2 раза и перераспределение элементов. Это также может вызвать преобразование деревьев обратно в списки.
• Пороговые значения:
  • TREEIFY_THRESHOLD = 8
  • UNTREEIFY_THRESHOLD = 6
  • MIN_TREEIFY_CAPACITY = 64

Важно: преобразование в дерево происходит только для бакетов с совпадающими хэш-кодами, но разными ключами (по equals). Если все ключи идентичны по equals, дерево не создается.

Таким образом, при переполнении бакета HashMap динамически адаптирует свою структуру для баланса между производительностью и потреблением памяти, используя либо односвязные списки, либо красно-черные деревья в зависимости от текущих условий.