Fale sobre colisões em HashMap.

Uma colisão em HashMap ocorre quando duas chaves diferentes têm o mesmo código hash. Isso não leva à perda de dados, mas afeta o desempenho.

Ao inserir um elemento:

1. É chamado hashCode() da chave.
2. O índice do balde no array é calculado com base no código hash.
3. Se o balde estiver vazio, o elemento é inserido.
4. Se o balde já contém elementos, equals() é chamado para cada elemento no balde com a nova chave.
5. Se equals() retornar true, o valor é atualizado.
6. Se equals() sempre retornar false, um novo elemento é adicionado ao balde.

Até o Android 7.0 (Nougat), HashMap usava listas encadeadas para resolver colisões. Com muitas colisões em um balde, a busca na lista encadeada torna-se O(n), onde n é o número de elementos no balde.

A partir do Android 7.0, para baldes com muitas colisões (limiar de 8 elementos), HashMap converte automaticamente a lista encadeada em uma árvore vermelho-preto (TreeNode). A busca na árvore tem complexidade O(log n), o que melhora significativamente o desempenho em casos de muitas colisões. Se o número de elementos no balde voltar a ser menor que o limiar (6 elementos), a árvore é convertida de volta em uma lista encadeada.

Uma boa implementação de hashCode() e equals() para objetos personalizados é fundamental para minimizar colisões e garantir a eficiência do HashMap.

Exemplo:

@Override
public int hashCode() {
    // Exemplo de uma boa implementação de hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Exemplo de implementação correta de equals
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    MyObject myObject = (MyObject) o;
    return field2 == myObject.field2 &&
           field1.equals(myObject.field1);
}