Pod kojim uslovima operacije u HashMap imaju vremensku složenost proporcionalnu veličini kolekcije?

Operacije u HashMap (na primer, get, put) obično imaju amortizovanu vremensku složenost O(1). Međutim, u nekim slučajevima, složenost može porasti do O(n), gde je n veličina kolekcije. To se dešava ako:

• Sve ključeve padnu u jedan kofu (bucket) zbog loše funkcije heširanja, što dovodi do duge liste ili stabla u jednoj ćeliji.
• Kolizije nisu ravnomerno raspoređene, i struktura podataka unutar kante degradira.

U Java 8 i novijim verzijama, ako u jednoj kanti ima previše elemenata, HashMap pretvara povezanu listu u uravnoteženo stablo (TreeNode), čime se najgori slučaj smanjuje na O(log n), ali ne i na O(1).

Stoga, operacije postaju proporcionalne veličini kolekcije pri jakim kolizijama i lošoj raspodeli heševa.