Una HashMap è una delle strutture dati più comunemente usate in Java, ed è nota per la sua efficienza. I dati in una HashMap sono memorizzati sotto forma di coppie chiave-valore.

In questo articolo, vi introducerei alle HashMap in Java. Esploriamo le operazioni comuni di HashMap e poi approfondiamo come funziona internamente. Otterrete un’idea della funzione hash e come avviene il calcolo dell’indice. Infine, guarderemo le complessità temporali delle operazioni e toccheremo brevemente il comportamento in un ambiente concorrente.

Cosa è una HashMap in Java?

Una HashMap implementa l’interfaccia Map, che fa parte del framework di raccolte Java. È basata sulla nozione dell’hash.

L’hash è un metodo che trasforma un input di dimensione arbitraria in un output di dimensione fissa usando una funzione hash. L’output generato si chiama codice hash e viene rappresentato da un valore intero in Java. I codici hash vengono usati per operazioni di ricerca e memorizzazione efficienti in una HashMap.

Operazioni Comuni

Come abbiamo discusso prima, i dati in una HashMap sono memorizzati sotto forma di coppie chiave-valore. La chiave è un identificatore univoco, e ogni chiave è associata ad un valore.

Ecco alcune operazioni comuni supportate da una HashMap. Scopriamo cosa fanno questi metodi con alcuni semplici esempi di codice:

Inserimento

  • Questo metodo inserisce una nuova coppia chiave-valore nella HashMap.

  • L’ordine di inserimento delle coppie chiave-valore non è mantenuto.

  • Durante l’inserimento, se una chiave è già presente, il valore esistente verrà sostituito con il nuovo valore passato.

  • È possibile inserire solo una chiave nulla nel HashMap, ma è possibile avere molti valori nulli.

La firma del metodo per questa operazione è riportata di seguito, seguita da un esempio:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

Nel codice soprastante, abbiamo un esempio di HashMap in cui aggiungiamo una chiave di tipo Stringa e un valore di tipo Integer.

Recupero:

  • Recupera il valore associato ad una chiave data.

  • Restituisce null se la chiave non esiste nel HashMap.

La firma del metodo per questa operazione è riportata di seguito, seguita da un esempio:

public V get(Object key)

Integer value = map.get("apple"); // restituisce 1

Nel codice soprastante, stiamo recuperando il valore associato alla chiave apple.

Altre operazioni comuni includono:

  • remove: rimuove il punto chiave-valore specificato. Restituisce null se la chiave non è trovata.

  • containsKey: Verifica se una chiave specifica è presente in HashMap.

  • containsValue: Verifica se un valore specifico è presente in HashMap.

Struttura interna di un HashMap

Internamente, un HashMap utilizza un array di cestini o bin. Ogni cestino è una lista collegata di tipo Node, utilizzata per rappresentare il punto chiave-valore di HashMap.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Sopra, puoi vedere la struttura della classe Node che viene utilizzata per memorizzare i punti chiave-valore di HashMap.

La classe Node ha i seguenti campi:

  • hash: si riferisce al hashCode della chiave.

  • key: si riferisce alla chiave del punto chiave-valore.

  • value: si riferisce al valore associato alla chiave.

  • next: Funge da riferimento al nodo successivo.

Il HashMap si basa fondamentalmente sull’implementazione di una tabella hash, e il suo rendimento dipende da due parametri chiave: la capacità iniziale e il fattore di carico. Le originali javadocs della classe Hash table definiscono questi due parametri come segue:

  • La capacità è il numero di cestini nella tabella hash, e la capacità iniziale è semplicemente la capacità alla creazione della tabella hash.

  • Il fattore di carico è un indicatore di quanto la tabella hash sia riempita prima che la sua capacità venga automaticamente aumentata.

Adesso proviamo a comprendere come funzionano le operazioni base, put e get, in un HashMap.

Funzione hash

Durante l’inserimento (`put`) di una coppia chiave-valore, la `HashMap` prima calcola il codice hash della chiave. La funzione hash poi computa un intero per la chiave. Le classi possono usare il metodo `hashCode` della classe `Object` o sovrascriverlo e fornire la loro implementazione personale. (Leggi il contratto del codice hash qui [link]). Il codice hash viene poi XOR-ato (eXclusive OR) con i suoi 16 bit superiori (h >> 16) per ottenere una distribuzione più uniforme.

L’XOR è un’operazione bitwise che confronta due bit, ottenendo 1 se i bit sono diversi e 0 se sono uguali. In questo contesto, eseguire un’operazione bitwise XOR tra il codice hash e i suoi 16 bit superiori (ottenuti usando l’operatore di shift a destra non negativo >>>>) aiuta a mescolare i bit, portando a un codice hash più uniformemente distribuito.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Sopra, puoi vedere il metodo hash statico della classe `HashMap`.

L’idea è avere un codice hash univoco per ogni chiave, ma la funzione hash potrebbe generare lo stesso codice hash per chiavi differenti. Questo porta ad una situazione nota come collisione. Vedremo come gestire le collisioni nella prossima sezione.

Calcolo dell’Indice

Una volta generato il codice hash per una chiave, la `HashMap` calcola un indice all’interno dell’array dei bucket per determinare dove memorizzare la coppia chiave-valore. Questo viene fatto usando un’operazione AND bitwise, che è un modo efficiente per calcolare il modulo quando la lunghezza dell’array è una potenza di due.

int index = (n - 1) & hash;

Qui, stiamo calcolando l’indice in base alla lunghezza dell’array delle caselle.

Una volta calcolato l’indice, la chiave viene memorizzata in quell’indice nell’array delle caselle. Tuttavia, se molte chiavi hanno lo stesso indice, si verifica una collisione. In questo scenario, il HashMap la gestisce in uno dei due seguenti modi:

  • Chaining/Linking: Ogni casella nell’array è una lista di nodi collegati. Se una chiave esiste già in un determinato indice e un’altra chiave viene hashata nello stesso indice, viene aggiunta alla lista.

  • Treeify: Se il numero di nodi eccede una certa soglia, la lista collegata viene convertita in un albero (Questo è stato introdotto in Java 8).

static final int TREEIFY_THRESHOLD = 8;

Questa è la soglia che determina la treeification.

Perciò, è essenziale avere una buona funzione hash che distribuisce uniformemente le chiavi attraverso le caselle e minimizza le probabilità di collisioni.

Le operazioni di recupero (get) e di eliminazione (remove) funzionano similmente all’operazione di inserimento (put). Ecco come:

  • Recupero (get): Calcola il codice hash utilizzando la funzione hash -> calcola l’indice utilizzando il codice hash -> percorre la lista collegata o l’albero per trovare il nodo con la chiave corrispondente.

  • Eliminazione (remove): Calcola il codice hash usando la funzione hash -> calcola l’indice usando il codice hash -> rimuove il nodo dalla lista linkata o dall’albero.

Complexità Temporale

Le operazioni base di un HashMap, come put, get e remove, offrono generalmente un tempo costante di O(1), supponendo che le chiavi siano distribuite uniformemente. In casi in cui la distribuzione delle chiavi è scarsa e ci sono molti conflitti, queste operazioni possono degradare ad una complessità lineare di O(n).

Sotto la treeification, dove lunghe catene di conflitti sono convertite in alberi equilibrati, le operazioni di ricerca possono migliorare ad una più efficiente complessità logaritmica di O(log n).

Sincronizzazione

L’implementazione di HashMap non è sincronizzata. Se molti thread accedono contemporaneamente ad un’istanza di HashMap e iterano sulla mappa, e se qualsiasi thread esegue una modifica strutturale (come l’aggiunta o la rimozione di una mappatura chiave-valore) sulla mappa, si verifica una ConcurrentModificationException.

Per evitare questo, è possibile creare un’istanza sicura a thread usando il metodo Collections.synchronizedMap.

Conclusione

In sintesi, capire le modalità di funzionamento interne di un HashMap è fondamentale per i sviluppatori per prendere decisioni informate. Sapere come una chiave viene mappata, come si verificano i conflitti e come possono essere evitati viene utile per usare il HashMap in maniera efficiente e efficace.