Onder welke voorwaarden hebben bewerkingen in HashMap een tijdcomplexiteit die evenredig is met de grootte van de collectie?

Operaties in HashMap (bijvoorbeeld, get, put) hebben meestal een geamortiseerde tijdscomplexiteit van O(1). Echter, in sommige gevallen kan de complexiteit oplopen tot O(n), waarbij n de grootte van de collectie is. Dit gebeurt als:

• Alle sleutels in één bak (bucket) terechtkomen vanwege een slechte hashfunctie, wat leidt tot een lange lijst of een boom in één cel.
• Collisies niet gelijkmatig verdeeld zijn, en de datastructuur binnen de bak degradeert.

In Java 8 en hoger, als er te veel elementen in één bak zijn, transformeert HashMap de gekoppelde lijst in een gebalanceerde boom (TreeNode), wat het slechtste geval reduceert tot O(log n), maar niet tot O(1).

Dus worden de operaties proportioneel aan de grootte van de collectie bij sterke collisies en slechte hashverdeling.