Millistel tingimustel on HashMap-i operatsioonidel ajakulude keerukus, mis on proportsionaalne kogumiku suurusega?

Operatsioonid HashMapis (näiteks get, put) on tavaliselt amortiseeritud ajakompleksusega O(1). Kuid mõnel juhul võib keerukus tõusta kuni O(n), kus n on kogumi suurus. See juhtub, kui:

• Kõik võtmed satuvad ühte ämbrisse (bucket) halva hash-funktsiooni tõttu, mis viib pika nimekirja või puu ühes rakus.
• Kollisioonid ei jaotu ühtlaselt ning andmestruktuur ämbris halveneb.

Java 8 ja uuemates versioonides, kui ühes ämbris on liiga palju elemente, muudab HashMap seotud nimekirja tasakaalustatud puuks (TreeNode), mis vähendab halvimat juhtumit O(log n)-le, kuid mitte O(1)-le.

Seega muutuvad operatsioonid proportsionaalseks kogumi suurusega tugevate kollisioonide ja halva hash-jaotuse korral.