Как работает вставка пары ключ-значение в HashMap (Java)?

Вставка элемента в HashMap<K, V> — это многоэтапный процесс, включающий вычисление хэша, разрешение коллизий и возможное изменение размера.

Алгоритм put(key, value) или putVal():

1. Вычисление хэша: Вызывается key.hashCode(), затем внутренняя функция hash() для дополнительного перемешивания бит, чтобы уменьшить коллизии.
2. Определение корзины (bucket): На основе хэша вычисляется индекс в массиве Node<K,V>[] table: index = (n - 1) & hash, где n — текущая ёмкость массива (степень двойки).
3. Вставка в корзину:
   • Корзина пуста: Создаётся новый узел Node и помещается по индексу.
   • Корзина занята (коллизия): Происходит проверка цепочки (список или дерево).
     • Если ключ первого узла совпадает (проверка через hash и equals), значение перезаписывается.
     • Если это узел-TreeNode (красно-чёрное дерево), вставка происходит в дерево.
     • Иначе идёт обход связного списка. Если ключ найден — значение обновляется. Если нет — новый узел добавляется в конец списка. Если длина списка превышает TREEIFY_THRESHOLD (8), список преобразуется в дерево.
4. Изменение размера (resize): Если общее количество элементов превышает threshold (capacity * loadFactor, по умолчанию 0.75), массив увеличивается вдвое, и все элементы перераспределяются (рехешируются).

Пример с кодом:

HashMap<String, Integer> map = new HashMap<>(16); // Начальная ёмкость 16, порог 12
map.put("apple", 1);
// 1. hash("apple") -> допустим, 12345
// 2. index = (16 - 1) & 12345 = 9
// 3. table[9] = new Node<>("apple", 1)

map.put("banana", 2); // Предположим, попадёт в другую корзину
map.put("apple", 3); // Найдёт узел с ключом "apple" в корзине 9, значение обновится на 3

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

• Иммutable ключи: Ключи должны быть неизменяемыми, так как изменение ключа после вставки нарушит логику хэширования.
• Производительность: В среднем O(1), но может деградировать до O(log n) при многих коллизиях (работа с деревом).