Kāda ir elementa meklēšanas sarežģītība pēc atslēgas HashMap?

Vidējā sarežģītība ir O(1), sliktākajā gadījumā — O(n).

• Vidējais gadījums (O(1)): Ar labu hašfunkciju un vienmērīgu elementu sadalījumu pa groziem (buckets), meklēšana samazinās līdz haškoda aprēķināšanai un tiešai piekļuvei attiecīgajam grozam masīvā. Iekš groza, ja nav kolīziju, elements tiek atrasts konstanta laika.
• Sliktākais gadījums (O(n)): Notiek, kad visi elementi ir hašoti tajā pašā grozā. Šādā gadījumā meklēšana kļūst par lineāru meklēšanu sasaistītā sarakstā (vai līdzsvarotā kokā Java 8+ gadījumā, ja ir daudz elementu grozā, bet pat koka pārlūkošana var aizņemt O(log n), un, ja ir daudz kolīziju, tas joprojām tuvojas O(n)).

No Java 8, ja grozs satur vairāk nekā noteiktu slieksni (TREEIFY_THRESHOLD, noklusējuma 8) elementu, sasaistītais saraksts tiek pārveidots līdzsvarotā kokā (sarkans-melns koks). Tas uzlabo sliktāko gadījumu meklēšanu vienā grozā līdz O(log n), bet, ja visi atslēgas ir ar vienādu hašu, kopējā meklēšana joprojām var būt tuvu O(n).