PrepBro
← Назад к вопросам

Меняется ли размер массива из Buckets в HashMap

1.7 Middle🔥 191 комментариев
#Коллекции

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Меняется ли размер массива из Buckets в HashMap?

Да, абсолютно меняется. Это один из ключевых механизмов HashMap — динамическое изменение размера (resizing/rehashing). Давайте разберемся подробно.

Краткий ответ

Массив buckets в HashMap растет динамически при достижении определенного процента заполнения. Это называется load factor (коэффициент нагрузки). По умолчанию, когда 75% массива заполнено, HashMap увеличивает размер в 2 раза и перехэшировует все элементы.

Как это работает

// Создание HashMap
Map<String, Integer> map = new HashMap<>();
// Начальная емкость: 16 buckets
// Load factor: 0.75

// Добавление элементов
map.put("key1", 1);
map.put("key2", 2);
// ...
map.put("key12", 12);  // 12 элементов из 16
// Еще не произошло resizing

map.put("key13", 13);  // Превышено 75% (16 * 0.75 = 12)
// BOOM! HashMap перестраивается:
// 1. Создается новый массив размером 32
// 2. Все 13 элементов перехэшируются (пересчитаны хэши)
// 3. Распределены по новым bucket'ам

Параметры HashMap

// Конструкторы HashMap

// 1. По умолчанию
Map<String, Integer> map1 = new HashMap<>();
// initialCapacity: 16
// loadFactor: 0.75
// threshold (порог): 12

// 2. С явной начальной емкостью
Map<String, Integer> map2 = new HashMap<>(100);
// initialCapacity: 100 (или ближайшая степень 2)
// loadFactor: 0.75
// threshold: 75

// 3. С явными параметрами
Map<String, Integer> map3 = new HashMap<>(50, 0.8f);
// initialCapacity: 50
// loadFactor: 0.8
// threshold: 40

Внутренняя структура HashMap

public class HashMap<K, V> extends AbstractMap<K, V> {
    
    // Массив buckets (корзин)
    transient Node<K, V>[] table;
    
    // Текущее количество элементов
    transient int size;
    
    // Коэффициент нагрузки (по умолчанию 0.75)
    final float loadFactor;
    
    // Порог, при котором происходит resize
    int threshold;
    
    // Каждый bucket — это цепь (linked list или red-black tree в Java 8+)
    static class Node<K, V> implements Map.Entry<K, V> {
        final K key;
        V value;
        Node<K, V> next;  // Для разрешения коллизий
    }
}

Процесс Resize (Rehashing)

// Упрощенный процесс resizing
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    
    // 1. Если таблица пуста, инициализируем
    if (table == null) {
        table = new Node[16];
    }
    
    // 2. Вставляем элемент
    if (++size > threshold) {
        // 3. Превышено пороговое значение!
        // Запускаем RESIZE
        resize();
    }
    
    return null;
}

final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = oldTab.length;
    int newCap = oldCap << 1;  // Увеличиваем в 2 раза (16 -> 32)
    
    // 1. Создаем новый массив большего размера
    Node<K, V>[] newTab = new Node[newCap];
    
    // 2. Перемещаем все элементы в новый массив
    for (int j = 0; j < oldCap; ++j) {
        Node<K, V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            
            if (e.next == null) {
                // Один элемент в bucket — простой случай
                newTab[e.hash & (newCap - 1)] = e;
            } else {
                // Несколько элементов — пересчет хэшей
                Node<K, V> loHead = null, loTail = null;
                Node<K, V> hiHead = null, hiTail = null;
                
                do {
                    int hi = e.hash & oldCap;
                    if (hi == 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 = e.next) != null);
                
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
    
    threshold = newThreshold;  // Обновляем порог
    return table = newTab;     // Устанавливаем новый массив
}

Пример: Визуализация процесса

// Шаг 1: HashMap с емкостью 16, loadFactor 0.75
HashMap<String, Integer> map = new HashMap<>();
threshold = 12  // 16 * 0.75

map.put("user1", 1);   // size = 1
map.put("user2", 2);   // size = 2
// ...
map.put("user12", 12); // size = 12 (еще ОК)

// Массив buckets: 16 слотов
// Заполнено: 12 слотов (75%)

// Шаг 2: Еще один элемент
map.put("user13", 13); // size = 13
// size (13) > threshold (12)!
// RESIZE:
// - Создается новый массив: 32 слота
// - threshold = 24 (32 * 0.75)
// - Все элементы перехэшируются
// - Теперь сложность операций улучшается

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

// Вставка (put) в HashMap:
// Средний случай: O(1) — прямой доступ
// Худший случай: O(n) — при collision chain
// После resize: O(1) благодаря лучшему распределению

// Важно:
// resize является дорогостоящей операцией O(n)
// Происходит редко, но когда происходит —
// может вызвать временное замедление

Оптимизация: задай начальную емкость

// Плохо: HashMap будет расширяться несколько раз
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put("key" + i, i);
    // При size = 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144
    // происходит resize (10+ раз!)
}

// Хорошо: задаем достаточную начальную емкость
Map<String, Integer> map = new HashMap<>(10000);
// Или с учетом loadFactor:
Map<String, Integer> map = new HashMap<>(10000, 0.75f);
// Все элементы влезут без resize

Сравнение: HashMap vs Hashtable vs ConcurrentHashMap

ХарактеристикаHashMapHashtableConcurrentHashMap
ResizeДа, динамическийДа, более затратныйДа, более сложный
LoadFactor0.750.75До 0.75
МногопоточностьНетДаДа
ПроизводительностьБыстраяМедленнаяБыстрая

Java 8+ оптимизация

// Java 8 добавила красно-черные деревья (Red-Black Trees)
// для больших цепей коллизий:

// Если в одном bucket'е более 8 элементов (TREEIFY_THRESHOLD)
// LinkedList преобразуется в TreeMap
// Это уменьшает сложность с O(n) до O(log n)

// Если bucket'е менее 6 элементов (UNTREEIFY_THRESHOLD)
// TreeMap преобразуется обратно в LinkedList

Важные константы HashMap

// Исходная емкость
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// Максимальная емкость
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

// Коэффициент нагрузки
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// Порог для преобразования LinkedList в Red-Black Tree
static final int TREEIFY_THRESHOLD = 8;

// Порог для преобразования Red-Black Tree в LinkedList
static final int UNTREEIFY_THRESHOLD = 6;

Практические рекомендации

  1. Предсказывай размер заранее:
// Если известен размер, задай начальную емкость
Map<String, User> users = new HashMap<>(expectedSize);
  1. Избегай многократных resizes:
// Плохо: множество resizes
Map<String, Integer> map = new HashMap<>();

// Хорошо: одна инициализация
Map<String, Integer> map = new HashMap<>((int)(expectedSize / 0.75) + 1);
  1. Учитывай loadFactor при оптимизации:
// Более высокий loadFactor = меньше памяти, но больше коллизий
Map<String, Integer> map = new HashMap<>(16, 0.9f);
// Риск: сам resize произойдет позже, но тем более дорого

Вывод

Да, размер массива buckets в HashMap МЕНЯЕТСЯ динамически. Это происходит автоматически при превышении порога нагрузки (по умолчанию 75% заполнения). HashMap удваивает размер и перестраивает индексы всех элементов. Это обеспечивает O(1) среднюю сложность операций, но требует оптимизации через задание начальной емкости в критических местах кода.

Меняется ли размер массива из Buckets в HashMap | PrepBro