При кои условия операциите в HashMap имат времева сложност, пропорционална на размера на колекцията?

Операциите в HashMap (например, get, put) обикновено имат амортизирана времева сложност O(1). Въпреки това, в някои случаи, сложността може да се увеличи до O(n), където n е размерът на колекцията. Това се случва, ако:

• Всички ключове попаднат в една кофа (bucket) поради лоша функция за хеширане, което води до дълъг списък или дърво в една клетка.
• Колизиите не са равномерно разпределени и структурата на данните вътре в кофата се деградира.

В Java 8 и по-нови версии, ако в една кофа има твърде много елементи, HashMap преобразува свързания списък в балансирано дърво (TreeNode), което намалява най-лошия случай до O(log n), но не и до O(1).

Следователно, операциите стават пропорционални на размера на колекцията при силни колизии и лошо разпределение на хешовете.