Erzählen Sie von Kollisionen in HashMap.

Eine Kollision in HashMap tritt auf, wenn zwei verschiedene Schlüssel denselben Hash-Code haben. Dies führt nicht zum Datenverlust, beeinflusst jedoch die Leistung.

Beim Einfügen eines Elements:

1. Wird hashCode() des Schlüssels aufgerufen.
2. Der Index des Buckets im Array wird basierend auf dem Hash-Code berechnet.
3. Wenn der Bucket leer ist, wird das Element eingefügt.
4. Wenn der Bucket bereits Elemente enthält, wird equals() für jedes Element im Bucket mit dem neuen Schlüssel aufgerufen.
5. Wenn equals() true zurückgibt, wird der Wert aktualisiert.
6. Wenn equals() immer false zurückgibt, wird ein neues Element zum Bucket hinzugefügt.

Bis Android 7.0 (Nougat) verwendete HashMap verkettete Listen zur Lösung von Kollisionen. Bei vielen Kollisionen in einem Bucket wird die Suche in der verketteten Liste O(n), wobei n die Anzahl der Elemente im Bucket ist.

Seit Android 7.0 wandelt HashMap für Buckets mit vielen Kollisionen (Schwelle 8 Elemente) automatisch die verkettete Liste in einen Rot-Schwarz-Baum (TreeNode) um. Die Suche im Baum hat eine Komplexität von O(log n), was die Leistung bei vielen Kollisionen erheblich verbessert. Wenn die Anzahl der Elemente im Bucket wieder unter die Schwelle (6 Elemente) fällt, wird der Baum wieder in eine verkettete Liste umgewandelt.

Eine gute Implementierung von hashCode() und equals() für benutzerdefinierte Objekte ist entscheidend, um Kollisionen zu minimieren und die Effizienz von HashMap zu gewährleisten.

Beispiel:

@Override
public int hashCode() {
    // Beispiel für eine gute hashCode-Implementierung
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Beispiel für eine korrekte equals-Implementierung
    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);
}