Wie hoch ist die Komplexität, ein Element anhand des Schlüssels in einer HashMap zu suchen?

Durchschnittliche Komplexität ist O(1), im schlimmsten Fall O(n).

• Durchschnittlicher Fall (O(1)): Bei einer guten Hash-Funktion und gleichmäßiger Verteilung der Elemente auf die Buckets reduziert sich die Suche auf die Berechnung des Hashs des Schlüssels und den direkten Zugriff auf den entsprechenden Bucket im Array. Innerhalb des Buckets, wenn keine Kollisionen vorliegen, ist das Element in konstanter Zeit gefunden.
• Schlimmster Fall (O(n)): Tritt auf, wenn alle Elemente in denselben Bucket gehasht werden. In diesem Fall wird die Suche zu einer linearen Suche in einer verketteten Liste (oder in einem balancierten Baum in Java 8+ für Buckets mit vielen Elementen, aber selbst das Durchlaufen des Baums kann O(log n) dauern, was bei vielen Kollisionen in einem Bucket immer noch an O(n) heranreicht, bezogen auf die Gesamtzahl der Elemente, wenn alle in denselben Bucket fallen).

Seit Java 8 wird für Buckets, die mehr als einen bestimmten Schwellenwert (TREEIFY_THRESHOLD, standardmäßig 8) an Elementen enthalten, die verkettete Liste in einen balancierten Baum (Rot-Schwarz-Baum) umgewandelt. Dies verbessert die schlimmste Fall-Suche innerhalb eines Buckets auf O(log n), aber wenn alle Schlüssel denselben Hash haben, kann die Gesamtsuche immer noch nahe bei O(n) liegen.