Vertel over botsingen in HashMap.

Een collision in HashMap treedt op wanneer twee verschillende sleutels dezelfde hash-code hebben. Dit leidt niet tot gegevensverlies, maar beïnvloedt de prestaties.

Bij het invoegen van een element:

1. Wordt hashCode() van de sleutel aangeroepen.
2. De index van de bak in de array wordt berekend op basis van de hash-code.
3. Als de bak leeg is, wordt het element ingevoegd.
4. Als de bak al elementen bevat, wordt equals() voor elk element in de bak met de nieuwe sleutel aangeroepen.
5. Als equals() true retourneert, wordt de waarde bijgewerkt.
6. Als equals() altijd false retourneert, wordt een nieuw element aan de bak toegevoegd.

Tot Android 7.0 (Nougat) gebruikte HashMap gekoppelde lijsten om collisions op te lossen. Bij veel collisions in één bak wordt gezocht in de gekoppelde lijst O(n), waarbij n het aantal elementen in de bak is.

Vanaf Android 7.0 converteert HashMap automatisch de gekoppelde lijst in een rode-zwart boom (TreeNode) voor bakken met veel collisions (drempel 8 elementen). Zoeken in de boom heeft complexiteit O(log n), wat de prestaties aanzienlijk verbetert bij veel collisions. Als het aantal elementen in de bak weer onder de drempel (6 elementen) komt, wordt de boom weer omgezet in een gekoppelde lijst.

Een goede implementatie van hashCode() en equals() voor aangepaste objecten is essentieel om collisions te minimaliseren en de efficiëntie van HashMap te waarborgen.

Voorbeeld:

@Override
public int hashCode() {
    // Voorbeeld van een goede hashCode-implementatie
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Voorbeeld van een correcte equals-implementatie
    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);
}