Qual è la velocità di ricerca in HashMap (media e peggiore)?

HashMap in Java garantisce un tempo medio di accesso a un elemento di circa O(1) grazie all'uso di una funzione hash per una ricerca rapida tramite chiave.

Tuttavia, nel caso peggiore, quando ci sono molte collisioni e tutti gli elementi finiscono in un unico bucket, la velocità di accesso può degradarsi a O(n), dove n è il numero di elementi nella mappa.

A partire da Java 8, quando ci sono molte collisioni all’interno di un bucket, la struttura dati cambia da una lista collegata a un albero bilanciato (TreeMap), migliorando il tempo di accesso peggiore a O(log n).

Esempio:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // Tempo medio O(1)