Kako se određuje vreme pristupa elementu u strukturi podataka HashMap?

Vreme pristupa elementu u strukturi podataka HashMap u Javi se obično smatra konstantnim — O(1). To se postiže korišćenjem hash funkcije koja pretvara ključ u indeks niza gde se čuva vrednost.

Međutim, u praksi, vreme pristupa može da se poveća do O(n) u najgorem slučaju, ako dođe do mnogo kolizija (različitih ključeva sa istim hash-om), i elementi se čuvaju u povezanoj listi ili stablu unutar jedne ćelije.

Od Java 8, da bi se smanjilo vreme pristupa pri kolizijama, povezana lista se pretvara u uravnoteženo stablo (TreeMap), što smanjuje vreme pretraživanja do O(log n) u takvim slučajevima.

Dakle, prosečno vreme pristupa je blizu O(1), ali u najgorem slučaju može biti O(log n) ili O(n).