Kāda ir HashMap elementu operāciju laika sarežģītība, un vai HashMap garantē norādīto sarežģītību elementa atlasei?

HashMap galveno operāciju (get, put, remove, containsKey) laika sarežģītība ir vidēji O(1).

Tas tiek panākts, izmantojot haštabulu, kurā elementi tiek glabāti šūnās (kastes), kas ir noteiktas pēc atslēgas haškoda. Ideālā gadījumā katrā kastē ir tikai viens elements.

Tomēr sliktākajā gadījumā, kad visi atslēgas ir ar vienādu haškodu vai notiek daudz kolīziju, elementi nonāk tajā pašā kastē. Šādā gadījumā kaste var pārvērsties saistītā sarakstā (līdz Java 8) vai kokā (Java 8 un jaunākās versijās, ja kastē ir vairāk nekā noteikts slieksnis). Darbības šādā kastē ir O(n), kur n ir elementu skaits tajā.

HashMap negarantē pastāvīgu laika sarežģītību O(1) pie elementa izgūšanas. Tā garantē tikai vidējo O(1). Sliktākajā gadījumā sarežģītība var būt O(n).

Faktori, kas ietekmē laika sarežģītību:

• Hash funkcijas kvalitāte: Labas hash funkcijas vienmērīgi sadala atslēgas pa kastēm, minimizējot kolīzijas.
• load factor (slodzes koeficients): Nosaka, cik pilna var būt haštabula, pirms tā izmērs tiek palielināts (rehash). Augsts load factor palielina kolīziju iespējamību.
• Sākotnējais ietilpīgums: Pārāk mazs sākotnējais ietilpīgums ar lielu elementu skaitu radīs biežas rehash operācijas, kas ir resursu ziņā dārgas.