Za akých podmienok majú operácie v HashMap časovú zložitosť úmernú veľkosti kolekcie?

Operácie v HashMap (napríklad, get, put) majú zvyčajne amortizovanú časovú zložitosť O(1). Avšak v niektorých prípadoch sa zložitosť môže zvýšiť na O(n), kde n je veľkosť kolekcie. K tomu dochádza, ak:

• Všetky kľúče padnú do jednej nádoby (bucket) kvôli zlej hashovacej funkcii, čo vedie k dlhému zoznamu alebo stromu v jednej bunke.
• Kolízie nie sú rovnomerne rozložené a dátová štruktúra vo vnútri nádoby sa degraduje.

V Java 8 a novších verziách, ak je v jednej nádobe príliš veľa prvkov, HashMap premení spojený zoznam na vyvážený strom (TreeNode), čo znižuje najhorší prípad na O(log n), ale nie na O(1).

Preto operácie sú proporcionálne veľkosti kolekcie pri silných kolíziách a zlej distribúcii hashov.