Koja je složenost pretraživanja elementa po ključe u HashMap?

Prosečna složenost je O(1), u najgorem slučaju — O(n).

• Prosečan slučaj (O(1)): Sa dobrom hash funkcijom i ravnomernom distribucijom elemenata po kanticama (buckets), pretraživanje se svodi na izračunavanje hash-a ključa i direktan pristup odgovarajućoj kanti u nizu. Unutar kante, ako nema kolizija, element se nalazi u konstantnom vremenu.
• Najgori slučaj (O(n)): Javlja se kada su svi elementi hash-ovani u istu kantu. U tom slučaju, pretraživanje postaje linearno pretraživanje u povezanoj listi (ili u uravnoteženom stablu u Java 8+ za kante sa mnogo elemenata, ali čak i prolazak kroz stablo može trajati O(log n), što pri mnogo kolizija u jednoj kanti i dalje približava O(n)).

Od Java 8, za kante koje sadrže više od određenog praga (TREEIFY_THRESHOLD, podrazumevano 8) elemenata, povezani spisak se pretvara u uravnoteženo stablo (crveno-crno stablo). To poboljšava najgori slučaj pretraživanja unutar jedne kante na O(log n), ali ako svi ključevi imaju isti hash, opšte pretraživanje i dalje može biti blizu O(n).