Care este complexitatea căutării unui element după cheie într-un HashMap?

Complexitatea medie este O(1), în cel mai rău caz — O(n).

• Caz mediu (O(1)): Cu o funcție hash bună și o distribuție uniformă a elementelor pe coșuri (buckets), căutarea se reduce la calcularea hash-ului cheii și accesul direct la coșul corespunzător din array. În interiorul coșului, dacă nu există coliziuni, elementul se găsește în timp constant.
• Caz cel mai rău (O(n)): Apare când toate elementele sunt hash-uite în același coș. În acest caz, căutarea devine o căutare liniară într-o listă legată (sau într-un arbore echilibrat în Java 8+ pentru coșurile cu mulți elemente, dar chiar și traversarea arborelui poate dura O(log n), ceea ce, în cazul multor coliziuni într-un singur coș, se apropie de O(n)).

Din Java 8, pentru coșurile care conțin mai mult decât un prag definit (TREEIFY_THRESHOLD, implicit 8) elemente, lista legată se transformă într-un arbore echilibrat (arbore roșu-negru). Acest lucru îmbunătățește cel mai rău caz de căutare în interiorul unui coș la O(log n), dar dacă toate cheile au același hash, căutarea generală poate fi în continuare aproape de O(n).