Что происходит внутри HashMap, когда вставляется новый ключ-значение?

Когда в HashMap вставляется новая пара ключ-значение, происходит следующее:

1. Вычисляется хэш-код ключа с помощью метода hashCode().
2. Хэш-код преобразуется в индекс массива (бэкенд HashMap — массив бакетов) с помощью операции, например, взятия остатка по размеру массива или битовой маски.
3. Если в бакете по этому индексу нет элементов, создаётся новая запись с ключом и значением.
4. Если бакет уже содержит элементы (коллизия), происходит обход цепочки (связного списка или дерева, если элементов много) для проверки, есть ли уже такой ключ:
   • Если ключ найден, значение обновляется.
   • Если ключа нет, новая запись добавляется в цепочку.
5. При достижении определённого порога заполнения (load factor) происходит расширение массива и перераспределение элементов (rehash).

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5); // Вычисляется hash("apple"), определяется индекс, вставляется запись