Aká je zložitosť vyhľadávania prvku podľa kľúča v HashMap?

Priemerná zložitosť je O(1), v najhoršom prípade — O(n).

• Priemerný prípad (O(1)): Pri dobrej hashovacej funkcii a rovnomernom rozložení prvkov do košov (buckets), sa vyhľadávanie znižuje na výpočet hash kľúča a priame získanie príslušného koša v poli. Vo vnútri koša, ak nie sú kolízie, je prvok nájdený v konštantnom čase.
• Najhorší prípad (O(n)): Nastáva, keď sú všetky prvky hashované do toho istého koša. V takom prípade sa vyhľadávanie stáva lineárnym prehľadávaním v prepojenej zozname (alebo v vyváženom strome v Java 8+ pre koše s veľkým počtom prvkov, ale aj prechádzanie stromom môže trvať O(log n), čo pri mnohých kolíziách v jednom koši stále približuje O(n)).

Od Java 8, pre koše obsahujúce viac ako určitý prah (TREEIFY_THRESHOLD, predvolene 8) prvkov, sa prepojený zoznam transformuje na vyvážené stromové štruktúry (červeno-čierne stromy). To zlepšuje najhorší prípad vyhľadávania v rámci jedného koša na O(log n), ale ak majú všetky kľúče rovnaký hash, celkové vyhľadávanie môže byť stále blízko O(n).