Za jakých podmínek mají operace v HashMap časovou složitost úměrnou velikosti kolekce?

Operace v HashMap (například get, put) mají obvykle amortizovanou časovou složitost O(1). Nicméně v některých případech může složitost vzrůst až na O(n), kde n je velikost kolekce. K tomu dochází, pokud:

• Všechny klíče spadnou do jednoho koše (bucket) kvůli špatné hashovací funkci, což vede k dlouhému seznamu nebo stromu v jedné buňce.
• Kolize nejsou rovnoměrně rozloženy a datová struktura uvnitř koše se degraduje.

V Java 8 a novějších verzích, pokud je v jednom koši příliš mnoho prvků, HashMap přemění spojový seznam na vyvážené stromové (TreeNode), což snižuje nejhorší případ na O(log n), ale nikoli na O(1).

Proto se operace stávají úměrné velikosti kolekce při silných kolizích a špatném rozložení hashů.