Come è strutturata e organizzata la struttura dati…

HashMap in Java si basa sui principi di hashing. Memorizza coppie "chiave-valore".

Struttura interna:

Array di bucket (contenitori). Ogni bucket è una lista collegata (o un albero, a partire da Java 8, quando ci sono molte collisioni).
Quando si aggiunge un elemento (put):
1. Si calcola il codice hash della chiave (key.hashCode()).
2. Il codice hash viene modificato per una distribuzione migliore (hash).
3. Usando l'hash modificato e la dimensione dell'array di bucket, si calcola l'indice del bucket (hash & (dimensione_array - 1)).
4. L'elemento (coppia "chiave-valore" come oggetto Node) viene inserito in quel bucket. Se il bucket contiene già elementi, il nuovo elemento viene aggiunto all'inizio della lista collegata o dell'albero.
5. Quando si aggiunge, si verifica se la chiave esiste già: si usa il metodo equals() per confrontare le chiavi nel bucket. Se la chiave viene trovata, il valore viene aggiornato.
Quando si recupera un elemento (get):
1. Si calcola anche l'indice del bucket in base alla chiave.
2. All'interno del bucket, si cerca l'elemento usando hashCode() e equals().
3. Viene restituito il valore associato.

Organizzazione:

Collisioni: Se più chiavi hanno lo stesso hash e finiscono nello stesso bucket, gli elementi sono memorizzati come lista collegata. Da Java 8, quando il numero di elementi nel bucket supera una soglia (solitamente 8), la lista viene trasformata in un albero per ricerche più veloci (O(log n) invece di O(n)).
Ridimensionamento: Quando il numero di elementi supera il "fattore di carico" (load factor * capacity), HashMap aumenta la dimensione dell'array interno di bucket (solitamente raddoppia) e ricalcola tutti gli hash. È un'operazione costosa (O(n)).
Parametri:
- capacity: dimensione iniziale dell'array di bucket (predefinito 16).
- load factor: soglia di carico (predefinito 0.75). Determina quando avviene il ridimensionamento.

Perché hashCode() e equals() sono importanti:

Il corretto funzionamento di HashMap dipende dalla corretta implementazione di questi metodi.
Se equals() restituisce true per due oggetti, allora hashCode() deve restituire lo stesso valore.
Un'implementazione errata può portare al fatto che gli elementi non vengano trovati (get restituirà null), anche se sono stati aggiunti.

Esempio di struttura Node:

// Solo interno
static class Node<K,V> implements Map.Entry<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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap offre operazioni di inserimento, recupero e rimozione rapide (in media O(1)) quando la distribuzione degli hash è uniforme. In caso di collisioni forti, l'operazione può diventare O(n) o O(log n) con gli alberi.

Non è thread-safe. Per l'uso in ambienti concorrenti, si dovrebbe usare ConcurrentHashMap o Collections.synchronizedMap(new HashMap<...>(...)).

Come è strutturata e organizzata la struttura dati HashMap in Java?