Aká je časová zložitosť operácie vyhľadávania prvku v HashMap v priemere?

V priemernom prípade operácia vyhľadávania prvku v HashMap v Jave má časovú zložitosť O(1) — konštantný čas.

Toho sa dosahuje použitím hash funkcie, ktorá vypočíta index koša (bucket) na uloženie dvojice kľúč-hodnota. Pri ideálnom rozložení prvkov medzi koše je vyhľadávanie priame.

Avšak v najhoršom prípade (napríklad pri veľkom počte kolízií) sa zložitosť môže zhoršiť na O(n), kde n je počet prvkov v HashMap, ak všetky prvky spadnú do jedného koša. Moderné implementácie Java (od Java 8) používajú vyvážené stromy (TreeNodes) vo vnútri košov pri veľkom počte kolízií, čo znižuje najhorší prípad na O(log n).

Väčšinou sa teda dá považovať, že vyhľadávanie v HashMap je operácia s amortizovanou zložitosťou O(1).