Kādās situācijās HashMap operācijas ir laika sarežģītība, kas ir proporcionāla kolekcijas izmēram?

HashMap operācijas (piemēram, get, put) parasti ir amortizētas laika sarežģītības O(1). Tomēr dažos gadījumos sarežģītība var pieaugt līdz O(n), kur n ir kolekcijas lielums. Tas notiek, ja:

• Visas atslēgas nonāk vienā mucā (bucket) sliktas hash funkcijas dēļ, kas noved pie garas saraksta vai koka vienā šūnā.
• Kolīzijas nav vienmērīgi sadalītas, un datu struktūra iekšpusē mucā degradējas.

Java 8 un jaunākās versijās, ja vienā mucā ir pārāk daudz elementu, HashMap pārvērš sasaistīto sarakstu līdzsvarotā kokā (TreeNode), kas samazina sliktāko gadījumu līdz O(log n), bet ne līdz O(1).

Tādēļ operācijas kļūst proporcionālas kolekcijas lielumam, ja ir spēcīgas kolīzijas un sliktas hash sadalījums.