Как увеличивается количество Bucket в HashMap

Как увеличивается количество Bucket в HashMap

HashMap — это одна из самых важных структур данных в Java. Понимание механизма изменения размера бакетов (resizing) критично для оптимизации производительности.

Что такое Bucket в HashMap

Bucket (корзина) — это массив ячеек, в которых хранятся entry (пары ключ-значение). При возникновении collision (когда несколько ключей имеют один хеш), используются цепочки (chains) или красно-чёрные деревья (в Java 8+).

// HashMap внутренне имеет такую структуру:
private Node<K,V>[] table; // массив buckets

// Каждый bucket содержит цепочку элементов
public class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // для коллизий
}

Процесс изменения размера HashMap

Размер HashMap динамически увеличивается когда количество элементов превышает load factor (коэффициент заполнения).

1. Load Factor

По умолчанию load factor = 0.75. Это означает:

HashMap<String, String> map = new HashMap<>();
// По умолчанию: initialCapacity = 16, loadFactor = 0.75

// Resize произойдёт когда:
// size > capacity * loadFactor
// size > 16 * 0.75 = 12

Например:

• capacity = 16 → resize произойдёт при 13-м элементе
• capacity = 32 → resize произойдёт при 25-м элементе
• capacity = 64 → resize произойдёт при 49-м элементе

2. Trigger для Resize

Резе срабатывает в методе putVal():

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

private void putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    // ... вставка элемента ...
    
    // Проверка условия для resize
    if (++size > threshold) {  // threshold = capacity * loadFactor
        resize();
    }
}

Процесс Resize

Когда условие size > threshold выполняется, вызывается метод resize():

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  // старая ёмкость
    int oldThr = threshold;  // старый threshold
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // ЖИМ СЛУЧАЙ: увеличение существующей таблицы
        if (oldCap >= MAXIMUM_CAPACITY) {  // MAXIMUM_CAPACITY = 1 << 30
            threshold = Integer.MAX_VALUE;  // не реsizе больше
            return oldTab;
        }
        // Увеличиваем ёмкость в 2 раза
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  // новый threshold тоже в 2 раза
    }
    else if (oldThr > 0) {
        // Если создали HashMap с указанной capacity
        newCap = oldThr;
    }
    else {
        // Инициализация по умолчанию
        newCap = DEFAULT_INITIAL_CAPACITY;  // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  // 12
    }
    
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (ft < MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE;
    }
    
    threshold = newThr;
    
    // Создаём новый массив buckets
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // ВАЖНО: перехешируем все элементы в новую таблицу
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // очищаем старый bucket
                
                if (e.next == null)
                    // Простой случай: один элемент
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // Если это красно-чёрное дерево
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // Есть коллизии: перестраиваем цепочку
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    
                    do {
                        next = e.next;
                        // Элементы распределяются в два bucket
                        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;  // размещение во втором полу
                    }
                }
            }
        }
    }
    return newTab;
}

Пример: Пошаговое увеличение размера

HashMap<String, Integer> map = new HashMap<>();  // capacity=16, threshold=12

// Добавляем элементы
map.put("a", 1);      // size=1
map.put("b", 2);      // size=2
map.put("c", 3);      // size=3
// ... добавляем до ...
map.put("l", 12);     // size=12 (всё ещё 16 buckets)
map.put("m", 13);     // size=13 > threshold(12)
                       // RESIZE! capacity: 16 → 32, threshold: 12 → 24

map.put("n", 14);     // size=14 (теперь 32 buckets)

Алгоритм переопределения позиции элемента

При resize каждый элемент перехешируется. Позиция вычисляется как:

int newIndex = hash & (newCapacity - 1);
// это то же самое что: hash % newCapacity
// но быстрее благодаря bitwise operation

Отличие от старого индекса:

int oldIndex = hash & (oldCapacity - 1);
int newIndex = hash & (newCapacity - 1);

// Элемент либо остаётся на месте:
if (oldIndex == newIndex)  // если (hash & oldCap) == 0
    // остаётся в первой половине новой таблицы
else
    // переходит во вторую половину
    newIndex = oldIndex + oldCapacity;

Параметры при создании HashMap

Можно оптимизировать, указав нужный размер:

// Плохо: будет много resizes
HashMap<String, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put("key" + i, "value" + i);
}

// Хорошо: указываем capacity заранее
// Нужен такой capacity, чтобы expectedSize < capacity * loadFactor
int capacity = (int)(1000 / 0.75f) + 1;  // ≈ 1334
HashMap<String, String> map2 = new HashMap<>(capacity);
for (int i = 0; i < 1000; i++) {
    map2.put("key" + i, "value" + i);
}

Временная сложность операций при resize

• put() без resize: O(1) в среднем
• put() с resize: O(n) — нужно перехешировать все n элементов
• Амортизированная сложность: O(1) — resize редко происходит

Tree vs List (Java 8+)

При много коллизиях HashMap оптимизирует хранение:

// Константы в HashMap
private static final int TREEIFY_THRESHOLD = 8;      // порог преобразования в дерево
private static final int UNTREEIFY_THRESHOLD = 6;   // порог преобразования обратно в список

// При resize, если цепочка имеет >= 8 элементов, она преобразуется в красно-чёрное дерево
// Это снижает временную сложность с O(n) до O(log n)

Факторы, влияющие на resize

1. Load Factor (по умолчанию 0.75)

   • Выше 0.75: меньше resize, но больше коллизий
   • Ниже 0.75: больше resize, но меньше коллизий

2. Начальная ёмкость (по умолчанию 16)

   • Для большого объёма данных: указать большую начальную ёмкость

3. Распределение хешей

   • Хорошее распределение хеш-функции уменьшает коллизии

Вывод

• HashMap увеличивает ёмкость в 2 раза когда size > capacity * loadFactor
• Resize вызывает перехеширование всех элементов, что O(n) операция
• Но это амортизируется, поэтому put() всё ещё O(1) в среднем
• Для оптимизации: создавай HashMap с нужной capacity заранее
• В Java 8+ используются деревья вместо цепочек при много коллизиях