По какому принципу увеличивается количество бакетов в хеш-таблице?

Количество бакетов в HashMap (а также в Hashtable, ConcurrentHashMap) увеличивается принципом удвоения при достижении определенного порога заполнения, называемого load factor.

Принцип увеличения происходит при вызове метода resize(). Этот метод вызывается, когда количество элементов (size) превышает произведение текущей емкости (capacity) на коэффициент загрузки (load factor).

• Initial Capacity (Начальная емкость): Количество бакетов при создании хеш-таблицы. По умолчанию 16.
• Load Factor (Коэффициент загрузки): Максимальная доля заполнения бакетов, при котором происходит увеличение емкости. По умолчанию 0.75.
• Threshold (Порог): Максимальное количество элементов, после которого произойдет ресайз. Рассчитывается как capacity * load factor.

Когда size > threshold, вызывается resize(). В процессе ресайза:

1. Создается новый массив бакетов с емкостью, в два раза превышающей текущую (newCapacity = oldCapacity * 2).
2. Все элементы из старого массива бакетов перехешируются и перераспределяются по новому массиву бакетов. Это необходимо, потому что хеш-функция, используемая для определения бакета, зависит от размера массива.
3. Обновляется значение threshold для новой емкости (newThreshold = newCapacity * load factor).

Пример псевдокода для resize():

// Примерный псевдокод
// Если size > threshold тогда...
int oldCapacity = table.length;
int newCapacity = oldCapacity << 1; // Удвоение емкости (oldCapacity * 2)

Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];

// Перехеширование и перенос элементов
for (int i = 0; i < oldCapacity; ++i) {
    Node<K,V> e;
    if ((e = table[i]) != null) {
        table[i] = null;
        if (e.next == null) {
            newTable[e.hash & (newCapacity - 1)] = e;
        } else {
            // Обработка связных списков или деревьев
            // ...логика перераспределения элементов из связного списка/дерева в новые бакеты
        }
    }
}

table = newTable; // Замена старого массива новым
threshold = (int)(newCapacity * loadFactor); // Обновление порога

Целью удвоения емкости является поддержание амортизированного постоянного времени для операций get и put. Удвоение гарантирует, что количество бакетов растет достаточно быстро, чтобы минимизировать коллизии при равномерном распределении хешей ключей. Слишком маленькое увеличение емкости приводило бы к частым ресайзам, что было бы неэффективно.