Jaká je složitost hledání prvku podle klíče v HashMap?

Průměrná složitost je O(1), v nejhorším případě — O(n).

• Průměrný případ (O(1)): S dobrým hashovacím funkcí a rovnoměrným rozložením prvků do košů (buckets) se hledání zjednodušuje na výpočet hash klíče a přímý přístup k odpovídajícímu koši v poli. Uvnitř koše, pokud nedochází ke kolizím, je prvek nalezen v konstantním čase.
• Nejhorší případ (O(n)): Nastává, když jsou všechny prvky hashovány do stejného koše. V takovém případě se hledání stává lineárním průchodem spojovaným seznamem (nebo v vyváženém stromu v Java 8+ pro koše s velkým počtem prvků, ale i průchod stromem může trvat O(log n), což při mnoha kolizích v jednom koši stále přibližně odpovídá O(n)).

Od Java 8 je pro koše obsahující více než určitou hranici (TREEIFY_THRESHOLD, výchozí 8) prvků spojovaný seznam transformován na vyvážené stromové struktury (Červeno-černý strom). To zlepšuje nejhorší případ hledání v rámci jednoho koše na O(log n), ale pokud mají všechny klíče stejný hash, může být celkové hledání stále blízko O(n).