Unter welchen Bedingungen haben Operationen in HashMap eine zeitliche Komplexität, die proportional zur Größe der Sammlung ist?

Operationen in HashMap (z.B. get, put) haben in der Regel eine amortisierte Laufzeitkomplexität von O(1). In einigen Fällen kann die Komplexität jedoch auf O(n) steigen, wobei n die Größe der Sammlung ist. Dies tritt auf, wenn:

• Alle Schlüssel in einem Bucket landen, aufgrund einer schlechten Hash-Funktion, was zu einer langen Liste oder einem Baum in einer Zelle führt.
• Kollisionen ungleichmäßig verteilt sind und die Datenstruktur im Bucket degradiert.

Ab Java 8 und höher wandelt HashMap bei zu vielen Elementen in einem Bucket die verkettete Liste in einen balancierten Baum (TreeNode) um, was den schlimmsten Fall auf O(log n) reduziert, aber nicht auf O(1).

Daher sind die Operationen proportional zur Größe der Sammlung bei starken Kollisionen und schlechter Hash-Verteilung.