Kokiose sąlygose HashMap operacijos turi laiko sudėtingumą, proporcingą kolekcijos dydžiui?

HashMap operacijos (pavyzdžiui, get, put) paprastai turi amortizuotą laiko sudėtingumą O(1). Tačiau kai kuriais atvejais sudėtingumas gali išaugti iki O(n), kur n yra kolekcijos dydis. Tai įvyksta, jei:

• Visos raktai patenka į vieną kibirą (bucket) dėl blogos hash funkcijos, kas sukelia ilgą sąrašą arba medį vienoje ląstelėje.
• Kolizijos nėra tolygiai paskirstytos, ir duomenų struktūra viduje kibiro blogėja.

Java 8 ir naujesnėse versijose, jei viename kibire yra per daug elementų, HashMap paverčia susietą sąrašą į subalansuotą medį (TreeNode), kas sumažina blogiausią atvejį iki O(log n), bet ne iki O(1).

Todėl operacijos tampa proporcingos kolekcijos dydžiui, esant stiprioms kolizijoms ir blogam hash paskirstymui.