O que acontece dentro do HashMap quando uma nova chave-valor é inserida?

Quando um novo par chave-valor é inserido num HashMap, o seguinte acontece:

1. O código hash da chave é calculado usando o método hashCode().
2. O código hash é transformado num índice do array (backend HashMap — array de buckets) através de uma operação, por exemplo, usando o resto da divisão pelo tamanho do array ou uma máscara de bits.
3. Se no bucket nesse índice não houver elementos, uma nova entrada com a chave e o valor é criada.
4. Se o bucket já contiver elementos (colisão), é percorrido o encadeamento (lista ligada ou árvore, se houver muitos elementos) para verificar se a chave já existe:
   • Se a chave for encontrada, o valor é atualizado.
   • Se a chave não existir, uma nova entrada é adicionada ao encadeamento.
5. Quando um determinado limite de preenchimento (fator de carga) é atingido, o array é expandido e os elementos são redistribuídos (rehash).

Exemplo:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5); // O hash("apple") é calculado, o índice é determinado, a entrada é inserida