Как работает метод put(key, value) в HashMap?

Метод put(K key, V value) добавляет или обновляет пару ключ-значение в HashMap. Его работа состоит из нескольких ключевых этапов:

Алгоритм (упрощенно для Java 8+):

1. Вычисление хеша: Вызывается key.hashCode(). Полученный хеш дополнительно обрабатывается внутренним методом hash() для «перемешивания» (чтобы младшие биты лучше распределялись) и уменьшения коллизий.
2. Определение бакета: На основе обработанного хеша вычисляется индекс бакета (ячейки внутреннего массива Node<K,V>[] table): index = (n - 1) & hash, где n — текущая длина массива (степень двойки).
3. Вставка в бакет:
   • Если бакет пуст: Создается новый узел Node и помещается в массив.
   • Если бакет не пуст: Происходит проверка цепочки (списка или дерева): a. Ключ существует: Сравнивается хеш и (через equals()) ключ первого узла. Если совпадает — значение перезаписывается. b. Коллизия: Если ключи разные, происходит обход цепочки.
     • В Java 8+ при небольшой длине цепочки используется связный список.
     • При превышении порога (TREEIFY_THRESHOLD = 8) и достаточной емкости таблицы список преобразуется в сбалансированное красно-черное дерево (TreeNode) для обеспечения сложности O(log n) в худшем случае.
4. Проверка размера: После добавления проверяется, не превышено ли отношение количества элементов к емкости (load factor, по умолчанию 0.75). Если превышено — запускается ресайз (rehashing): емкость массива увеличивается вдвое, все элементы перераспределяются по новым бакетам.

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1); // Хеш "apple" -> индекс бакета -> вставка новой ноды.
map.put("banana", 2); // Вставка в другой (возможно, тот же) бакет.
map.put("apple", 3); // Хеш "apple" -> тот же индекс -> найдена нода с ключом "apple" -> значение обновлено на 3.

Итог: put() обеспечивает амортизированную сложность O(1) благодаря хешированию, но в худшем случае (все ключи попали в один бакет до Java 8) могла деградировать до O(n). В Java 8+ с деревьями худший случай улучшен до O(log n).