Java HashMap

HashMap<K, V> è l'implementazione Map predefinita nel JDK e la struttura dati più utilizzata nel codice applicativo Java. È alla base di HashSet (che è una HashMap con tutti i valori impostati su un singolo dummy), è ciò che Collectors.toMap costruisce, ed è la struttura dietro ogni "tabella di lookup" che scrivi quando non hai bisogno di ordinamento o concorrenza. Le operazioni hanno una complessità attesa O(1) — un hash, un indice di bucket, uno o due controlli equals — indipendentemente dalla dimensione.

Operazioni principali

Questi sono i metodi che usi quotidianamente. Ognuno ha complessità attesa O(1).

Itera sulle voci (non sulle chiavi, quando hai bisogno anche dei valori) per evitare una seconda ricerca per ogni chiave:

Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 90);
scores.put("bob", 75);

for (Map.Entry<String, Integer> e : scores.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

// Or the lambda form:
scores.forEach((name, score) -> System.out.println(name + " -> " + score));

Come è strutturata la tabella

Una HashMap mantiene un array di bucket di dimensione pari a una potenza di due. L'inserimento di una voce compie cinque operazioni:

1. Calcola h = hashCode(key). Mescola i 16 bit superiori e inferiori insieme — h ^ (h >>> 16) — in modo che un hash come 0x12340000 non perda i bit superiori durante la maschera.
2. Maschera: i = h & (table.length - 1). Equivale a h mod length per lunghezze potenza di due, ed è più veloce dell'operatore modulo.
3. Percorre la catena in table[i]. Se esiste un nodo con una chiave uguale, sovrascrive il suo valore e restituisce quello vecchio.
4. Altrimenti, aggiunge (o, da Java 8, in coda) un nuovo nodo.
5. Se size > capacity * loadFactor, ridimensiona: raddoppia la tabella e ri-distribuisce ogni voce.

Fino a Java 7 la catena di bucket era una lista concatenata singola, e basta. Da Java 8 in poi, quando una catena raggiunge otto voci, il bucket viene convertito in un piccolo albero bilanciato (un albero rosso-nero) indicizzato dall'hash. La ricerca in quel bucket diventa O(log n) invece di O(n), il che limita i danni di un attacco denial-of-service che genera hash in collisione. Se l'albero si riduce a sei o meno voci, torna ad essere una lista. Non vedrai questo nel codice normale — conta solo quando il tuo hashCode è avversariale o patologicamente pessimo.

Capacità, fattore di carico e pre-dimensionamento

Stesse impostazioni di HashSet:

• Capacità iniziale — predefinita 16, arrotondata alla potenza di due successiva.
• Fattore di carico — predefinito 0.75. Quando size > capacity * 0.75, la tabella raddoppia.

Se conosci la dimensione in anticipo, pre-dimensiona:

Map<String, User> users = new HashMap<>(expectedSize * 4 / 3); // skip the doublings

Oppure, da Java 19, la factory esplicita:

Map<String, User> users = HashMap.newHashMap(expectedSize);

Questa è l'espressione più chiara dell'intento — calcola la capacità iniziale corretta a partire da una dimensione target in modo che la tabella non debba crescere.

Chiavi null e valori null

HashMap consente una chiave null (è memorizzata nel bucket 0 con hash 0) e un numero qualsiasi di valori null. Questo è un vantaggio rispetto a Hashtable (che rifiuta entrambi), ma offusca il significato di get(k) == null:

m.put("key", null);
m.get("key");          // returns null
m.containsKey("key"); // returns true

Il costo di disambiguazione è reale. È preferibile non memorizzare valori null; usa Optional, un valore sentinella, o semplicemente ometti la chiave. La factory Map.of(...) di Java 9+ lo impone per te.

hashCode e equals sono il tuo contratto

Inserire la propria classe in una HashMap funziona solo se hashCode e equals sono coerenti. Le stesse regole di HashSet:

• Oggetti uguali devono avere codici hash uguali.
• Oggetti diversi possono collidere (va bene, è per questo che i bucket sono catene).
• Mutare una chiave dopo l'inserimento è un comportamento indefinito.

Usa un record se puoi — entrambi i metodi vengono generati correttamente. Oppure lascia che l'IDE li generi. Non scrivere mai hashCode a mano se puoi evitarlo.

record UserId(String tenant, String localPart) {}
Map<UserId, User> directory = new HashMap<>();
directory.put(new UserId("acme", "alice"), new User(/*...*/));
directory.get(new UserId("acme", "alice")); // hit

Ordine di iterazione — esplicitamente indefinito

HashMap non garantisce l'ordine di iterazione. L'ordine dipende dalla disposizione dei bucket, che dipende dall'hash, dalla capacità e dalla cronologia dei ridimensionamenti — può cambiare tra un'esecuzione e l'altra e tra versioni JVM. Se fai affidamento sull'ordine, il tuo codice è errato; se i tuoi test fanno affidamento sull'ordine, sono instabili.

Se l'ordine di iterazione è importante, usa LinkedHashMap per l'ordine di inserimento o TreeMap per l'ordine ordinato. Entrambi sono sostituti diretti.

Non thread-safe

HashMap si corromperà sotto mutazione concorrente — e storicamente una modalità di fallimento notoriamente grave era un ciclo infinito durante un ridimensionamento concorrente. Non condividere una HashMap tra thread. La struttura corretta per il codice multi-thread è ConcurrentHashMap (trattata più avanti nella parte sulla concorrenza). Collections.synchronizedMap(new HashMap<>()) esiste ma utilizza un singolo lock per ogni operazione, il che è più lento e raramente la risposta giusta.

Un esempio pratico: contatore, tabella di lookup e gli idiomi moderni

Il programma seguente utilizza una HashMap in diversi modi: un contatore di parole tramite merge, una cache di memoizzazione ricorsiva, una dimostrazione dell'ambiguità dei valori null, la factory newHashMap di Java 19, e un record come chiave composita.

Cosa trarre dall'esecuzione:

• merge condensa i tre passaggi "get, default-o-aggiungi-uno, put" in una sola chiamata. Usalo ogni volta che mantieni un contatore o una somma per chiave.
• La cache Fibonacci trasforma una ricorsione esponenziale in una lineare: controlla la mappa, ricorre in caso di mancata corrispondenza, poi put il risultato. Nota che usa get + put invece di computeIfAbsent — una computeIfAbsent ricorsiva muta la mappa mentre la sua stessa funzione di mappatura è ancora in esecuzione, e da Java 9 questo lancia ConcurrentModificationException. Riserva computeIfAbsent per le ricerche non ricorsive di tipo "carica-o-calcola".
• L'ambiguità del valore null è reale. get ha restituito null sia per una chiave presente che per una assente nello stesso modo. L'unico modo per distinguerle è containsKey — o decidendo di non memorizzare null in primo luogo.
• Il pre-dimensionamento con HashMap.newHashMap(1_000_000) consente a un milione di inserimenti di completarsi senza alcun rehash — la tabella parte dalla capacità giusta.
• Il record UserId fornisce equals/hashCode corretti gratuitamente. Questo è il modo moderno per comporre chiavi di hash-map da più campi.

Cosa c'è dopo

HashMap non garantisce l'ordine di iterazione. Se hai bisogno che l'ordine di inserimento venga ricordato — ad esempio stai serializzando la mappa in JSON e vuoi un output stabile — lo strumento giusto è LinkedHashMap. È anche la base di una cache LRU classica, che trattiamo nello stesso capitolo.

Pratica