Qual è la complessità di cercare un elemento per chiave in una HashMap?

La complessità media è O(1), nel peggiore dei casi è O(n).

• Caso medio (O(1)): Con una buona funzione hash e una distribuzione uniforme degli elementi nei contenitori (buckets), la ricerca si riduce a calcolare l'hash della chiave e accedere direttamente al contenitore corrispondente nell'array. All’interno del contenitore, se non ci sono collisioni, l’elemento si trova in tempo costante.
• Caso peggiore (O(n)): Si verifica quando tutti gli elementi vengono hashati nello stesso contenitore. In tal caso, la ricerca diventa una ricerca lineare in una lista collegata (o in un albero bilanciato in Java 8+ per contenitori con molti elementi, ma anche attraversare l’albero può richiedere O(log n), che in presenza di molte collisioni in un singolo contenitore si avvicina comunque a O(n)).

A partire da Java 8, per i contenitori che contengono più di una soglia definita (TREEIFY_THRESHOLD, di default 8) elementi, la lista collegata viene trasformata in un albero bilanciato (Albero Rosso-Nero). Questo migliora il caso peggiore di ricerca all’interno di un singolo contenitore a O(log n), ma se tutte le chiavi hanno lo stesso hash, la ricerca complessiva può comunque essere vicina a O(n).