Как работает HashMap в Java при добавлении элемента (put)?

Алгоритм добавления элемента put(key, value) в HashMap:

1. Вычисление хеша: Вызывается key.hashCode() для получения начального хеш-кода. Затем внутри HashMap применяется дополнительная функция hash() для «смешивания» битов, чтобы уменьшить коллизии.
2. Определение корзины (bucket): На основе итогового хеша вычисляется индекс в массиве корзин: index = (n - 1) & hash, где n — текущая длина массива (всегда степень двойки).
3. Вставка в корзину:
   • Корзина пуста: Создается новый узел Node<K,V> и помещается по вычисленному индексу.
   • Корзина не пуста (коллизия): Происходит итерация по цепочке в корзине (связный список или дерево). Для каждого узла проверяется:
     • Ключи совпадают: Если хеши равны И (key == node.key или key.equals(node.key)), значение в существующем узле перезаписывается.
     • Ключи разные: Процесс продолжается до конца цепочки.
4. Структура разрешения коллизий (Java 8+):
   • Если цепочка короткая — используется связный список.
   • Если длина цепочки превышает порог (TREEIFY_THRESHOLD = 8) И общий размер массива больше MIN_TREEIFY_CAPACITY = 64, список преобразуется в сбалансированное красно-черное дерево (TreeNode). Это улучшает производительность с O(n) до O(log n) при большом числе коллизий.
5. Увеличение размера (resize): Если общее количество элементов превышает capacity * loadFactor (по умолчанию 16 * 0.75 = 12), массив корзин увеличивается в 2 раза, и все элементы перераспределяются (rehash).

Пример и важные детали:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 10); // 1. hash("key1") -> index, 2. Создание Node.
map.put("key2", 20); // Возможная коллизия, если index совпал с key1.
map.put("key1", 30); // Ключ совпал -> значение перезаписано с 10 на 30.

// Критически важно для ключей-объектов:
// - Корректно переопределять equals() и hashCode().
// - Хеш-функция должна давать равномерное распределение.