Что происходит при вставке пары ключ-значение в HashMap

Процесс вставки пары ключ-значение в HashMap

Вставка в HashMap — это не просто добавление. Это сложный алгоритм, который использует хеширование, распределение в bucket'ы, обработку коллизий и даже преобразование структуры для оптимизации. Разберемся пошагово.

Высокоуровневый процесс

hashMap.put(key, value)
   ↓
1. Вычислить hash(key)
   ↓
2. Найти bucket: hash % capacity
   ↓
3. Искать key в bucket'е
   ↓
4. Если найден → обновить value
   Если не найден → добавить Entry
   ↓
5. Если bucket слишком заполнен → resize() и rehash

Пошаговый процесс

Шаг 1: Вычисление хеша

Java вызывает hashCode() на ключе:

int hash = key.hashCode();

Проблема: hashCode() может вернуть любое число (от -2^31 до 2^31 - 1). Решение: нужно преобразовать в индекс массива.

Шаг 2: Вычисление индекса bucket'а

Наивный подход (используется в некоторых реализациях):

int index = hash % capacity;  // ❌ Может дать отрицательный индекс

Правильный подход (Java):

int hash = hash(key.hashCode());  // Улучшенная хеш-функция
int index = hash & (capacity - 1);  // Эквивалент hash % capacity, но для степеней двойки

private static final int hash(Object key) {
    int h;
    // Смешиваем биты для лучшего распределения
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Почему это важно? Хорошее распределение означает, что элементы равномерно разбросаны по bucket'ам.

Шаг 3: Поиск элемента в bucket'е

HashMap внутренне использует массив Node'ов:

private class Node<K, V> {
    final K key;
    V value;
    Node<K, V> next;  // Linked list для коллизий
    int hash;
}

// Массив bucket'ов
Node<K, V>[] table = new Node[capacity];

Поиск в bucket'е (linked list с коллизиями):

Node<K, V> node = table[index];
while (node != null) {
    if (node.hash == hash && node.key.equals(key)) {
        return node;  // Нашли!
    }
    node = node.next;  // Переходим к следующему
}

Шаг 4: Вставка или обновление

Если элемент найден:

V oldValue = node.value;
node.value = value;  // Обновляем значение
return oldValue;     // Возвращаем старое значение

Если элемент не найден:

Node<K, V> newNode = new Node<>(hash, key, value, table[index]);
table[index] = newNode;  // Добавляем в начало linked list'а
size++;                  // Увеличиваем счетчик размера

Шаг 5: Проверка load factor и resize

Load Factor = size / capacity

По умолчанию: 0.75 (75% заполнения)

if (size > capacity * loadFactor) {
    resize();  // Расширяем таблицу
}

Пример: вставка с визуализацией

Представим HashMap с capacity = 4 (индексы 0, 1, 2, 3):

HashMap<String, Integer> map = new HashMap<>(4);

// 1. Вставляем ("Alice", 25)
hash("Alice") % 4 = 1
table[1] = Node("Alice", 25, null)
// Состояние: [null, Node(Alice,25), null, null]

// 2. Вставляем ("Bob", 30)
hash("Bob") % 4 = 3
table[3] = Node("Bob", 30, null)
// Состояние: [null, Node(Alice,25), null, Node(Bob,30)]

// 3. Вставляем ("Charlie", 35)
hash("Charlie") % 4 = 1  // Коллизия!
table[1] = Node("Charlie", 35, Node(Alice,25))  // Добавляем в начало
// Состояние: [null, Node(Charlie,35) -> Node(Alice,25), null, Node(Bob,30)]

// 4. Обновляем ("Alice", 26)
hash("Alice") % 4 = 1
// Ищем Alice в linked list'е на позиции 1
// Находим: Node(Alice,25) -> обновляем на 26
// Состояние: [null, Node(Charlie,35) -> Node(Alice,26), null, Node(Bob,30)]

Полный код вставки (упрощенная версия)

public V put(K key, V value) {
    // Шаг 1: Вычислить hash
    int hash = hash(key);
    
    // Шаг 2: Вычислить индекс
    int index = hash & (table.length - 1);
    
    // Шаг 3: Ищем существующий элемент
    Node<K, V> node = table[index];
    while (node != null) {
        if (node.hash == hash && 
            (node.key == key || key.equals(node.key))) {
            // Найден! Обновляем
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node = node.next;
    }
    
    // Шаг 4: Не найден, добавляем новый Node
    Node<K, V> newNode = new Node<>(hash, key, value, table[index]);
    table[index] = newNode;
    size++;
    
    // Шаг 5: Проверяем load factor
    if (size >= table.length * loadFactor) {
        resize();
    }
    
    return null;
}

Коллизии и их обработка

Коллизия — когда два разных ключа имеют одинаковый hash % capacity.

Rешение Java: Separate Chaining (chaining with linked list)

// Коллизия
hash("Alice") % 4 = 1
hash("Adam")  % 4 = 1

// Оба в одном bucket'е (linked list)
table[1]: Alice -> Adam

Оптимизация в Java 8+: если bucket становится слишком большим (>= 8), linked list преобразуется в Red-Black Tree:

if (binCount >= TREEIFY_THRESHOLD) {
    treeifyBin(tab, hash);  // Преобразуем в дерево
}

Это снижает сложность поиска с O(n) до O(log n).

Процесс resize() и rehashing

Когда load factor превышен:

private void resize() {
    // Новый capacity = старый × 2
    int newCapacity = table.length * 2;
    Node<K, V>[] newTable = new Node[newCapacity];
    
    // Перемещение всех элементов
    for (int i = 0; i < table.length; i++) {
        Node<K, V> node = table[i];
        while (node != null) {
            // Пересчитываем индекс с новым capacity
            int newIndex = node.hash & (newCapacity - 1);
            
            Node<K, V> next = node.next;  // Сохраняем следующий
            node.next = newTable[newIndex];  // Переставляем
            newTable[newIndex] = node;
            
            node = next;
        }
    }
    
    table = newTable;
}

Временная сложность resize: O(n), где n — количество элементов.

Практический пример: отслеживание вставки

class VerboseHashMap<K, V> extends HashMap<K, V> {
    @Override
    public V put(K key, V value) {
        System.out.println("Вставляем: " + key + " -> " + value);
        System.out.println("  hash = " + key.hashCode());
        System.out.println("  index = " + (key.hashCode() % 16));
        
        V oldValue = super.put(key, value);
        
        if (oldValue == null) {
            System.out.println("  Новый элемент");
        } else {
            System.out.println("  Обновление (было: " + oldValue + ")");
        }
        
        return oldValue;
    }
}

// Использование
VerboseHashMap<String, Integer> map = new VerboseHashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
map.put("Alice", 26);  // Обновление

Временные сложности операции put()

Типичное распределение

С хорошо распределенными hash'ами и load factor 0.75:

// Средние длины цепей при 1000 элементов и capacity 1024
Большинство bucket'ов: 0-1 элемент
Вероятность коллизии: низкая
Производительность: близка к O(1)

Ключевые моменты

1. hashCode() вычисляется один раз
2. Индекс вычисляется как hash & (capacity - 1)
3. Коллизии решаются linked list'ом (или деревом в Java 8+)
4. Resize происходит при size > capacity × 0.75
5. Rehashing пересчитывает индексы для всех элементов
6. Временная сложность: O(1) в среднем, O(n) в худшем

Понимание этого процесса помогает:

• Выбирать правильный load factor
• Писать хорошие hashCode() методы
• Отлаживать проблемы с производительностью
• Избегать ошибок с изменяемыми ключами