Como é implementado o tratamento de colisões no HashMap quando diferentes chaves têm o mesmo código hash?

No Java, o tratamento de colisões no HashMap quando os códigos de hash são iguais é implementado usando encadeamento (chaining). Isso significa que todos os elementos cujo código de hash leva ao mesmo índice no array de buckets são armazenados numa lista ligada ou numa árvore (a partir do Java 8) nesse bucket.

Se o número de elementos na cadeia se tornar suficientemente grande (padrão acima de 8), a lista ligada é transformada numa árvore balanceada (TreeNode), o que melhora o desempenho de busca de O(n) para O(log n).

Exemplo de lógica de inserção simplificada:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Verifica se a chave já existe na cadeia
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // atualiza o valor
        return;
    }
    head = head.next;
}
// Se a chave não existir, adiciona um novo nó ao início da lista
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Desta forma, o HashMap lida eficazmente com colisões, mantendo um desempenho aceitável.