În ce condiții operațiile în HashMap au o complexitate de timp proporțională cu dimensiunea colecției?

Operațiile în HashMap (de exemplu, get, put) au, în general, o complexitate temporară amortizată de O(1). Cu toate acestea, în unele cazuri, complexitatea poate crește până la O(n), unde n este dimensiunea colecției. Acest lucru se întâmplă dacă:

• Toate cheile cad într-un singur coș (bucket) din cauza unei funcții de hash slabe, ceea ce duce la o listă lungă sau la un arbore într-o singură celulă.
• Coliziunile nu sunt distribuite uniform, iar structura de date din interiorul coșului se degradează.

În Java 8 și versiunile ulterioare, dacă într-un coș sunt prea multe elemente, HashMap transformă lista legată într-un arbore echilibrat (TreeNode), ceea ce reduce cel mai rău caz la O(log n), dar nu la O(1).

Prin urmare, operațiile devin proporționale cu dimensiunea colecției în caz de coliziuni puternice și distribuție slabă a hash-urilor.