Kokia yra HashMap elementų operacijų laiko sudėtingumas, ir ar HashMap garantuoja nurodytą sudėtingumą elemento paieškai?

HashMap pagrindinių operacijų (get, put, remove, containsKey) laiko sudėtingumas vidutiniškai yra O(1).

Tai pasiekiama naudojant maišos lentelę, kurioje elementai saugomi skyriuose (krepšiuose), kurie nustatomi pagal rakto maišos kodą. Idealiu atveju kiekviename krepšyje yra tik vienas elementas.

Tačiau blogiausiu atveju, kai visi raktai turi tą patį maišos kodą arba įvyksta daug kolizijų, elementai patenka į tą patį krepšį. Tokiu atveju, krepšys gali virsti susietu sąrašu (iki Java 8) arba medžiu (Java 8 ir naujesnėse versijose, jei elementų skaičius krepšyje viršija tam tikrą slenkstį). Operacijos tokio krepšio metu turi laiko sudėtingumą O(n), kur n yra elementų skaičius tame krepšyje.

HashMap negarantuoja pastovaus laiko sudėtingumo O(1) elementų gavimui. Ji garantuoja tik vidutinį O(1) laiką. Blogiausiu atveju, sudėtingumas gali būti O(n).

Veiksniai, turintys įtakos laiko sudėtingumui:

• Hash funkcijos kokybė: Geras hash funkcija tolygiai paskirsto raktus po krepšius, minimalizuodama kolizijas.
• load factor (apkrovos koeficientas): Nustato, kaip pilna gali būti hash lentelė iki jos dydžio padidinimo (rehash). Aukštas load factor gali padidinti kolizijų tikimybę.
• Pradinis talpumas: Per mažas pradinis talpumas su daug elementų sukels dažnus rehash'us, kas yra išteklių reikalaujanti operacija.