Wie wird die Effizienz der Suche nach einem Element anhand des Schlüssels in einer HashMap bei Kollisionen bewertet?

In HashMap erfolgt die Suche nach einem Element anhand des Schlüssels im Durchschnitt in O(1), aber bei Kollisionen hängt die Effizienz von der Art der Behandlung ab.

Früher wurden Kollisionen mit Verkettungen (verkettete Listen) behandelt, und im schlimmsten Fall (wenn alle Schlüssel in einem Korb landen) wurde die Suche zu O(n).

Seit Java 8 wird, wenn die Anzahl der Elemente in einem Korb einen bestimmten Schwellenwert überschreitet, die verkettete Liste in einen balancierten Baum (z.B. Rot-Schwarz-Baum) umgewandelt. Dies verbessert den schlimmsten Fall der Suche auf O(log n) für diesen Korb.

Daher:

• Bei wenigen Kollisionen bleibt die Suche nahe bei O(1).
• Bei vielen Kollisionen in einem Korb ist die Suche O(log n).

Diese Verbesserung erhöht die Leistung von HashMap in ungünstigen Szenarien erheblich.