Koja je vremenska složenost operacija nad elementima u HashMap, i garantuje li HashMap zadatu složenost pri izboru elementa?

Vremenska složenost osnovnih operacija (get, put, remove, containsKey) u HashMap prosečno je O(1).

Ovo se postiže korišćenjem hash tabele, gde su elementi smešteni u ćoškove (kante) određene hash kodom ključa. U idealnom slučaju, svaka kanta sadrži jedan element.

Međutim, u najgorem slučaju, kada svi ključevi imaju isti hash kod ili dolazi do mnogo kolizija, elementi se smeštaju u istu kantu. U tom slučaju, kanta može postati povezani spisak (do Java 8) ili drvo (Java 8 i više, ako broj elemenata u kanti pređe određeni prag). Operacije na takvoj kanti imaju vremensku složenost O(n), gde n predstavlja broj elemenata u njoj.

HashMap ne garantuje konstantnu vremensku složenost O(1) pri preuzimanju elementa. Garantuje samo prosečnu složenost O(1). U najgorem slučaju, složenost može biti O(n).

Faktori koji utiču na vremensku složenost:

• Kvalitet hash funkcije: Dobra hash funkcija ravnomerno raspoređuje ključeve po kantama, minimizirajući kolizije.
• load factor (faktor opterećenja): Određuje koliko može biti popunjena hash tabela pre nego što se poveća njen kapacitet (rehash). Visok load factor može povećati verovatnoću kolizija.
• Početni kapacitet: Prevelik početni kapacitet sa velikim brojem elemenata izazvaće česte rehash operacije, što je resursno zahtevno.