Java Academy · Lezione

Come funziona HashMap

Bucket, hashing e collisioni

Come funziona HashMap è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

Che cosa memorizza HashMap

Una HashMap memorizza coppie chiave-valore e offre operazioni di ricerca, inserimento e rimozione con costo medio O(1).

Internamente mantiene un array chiamato tabella. Ogni posizione di questo array è chiamata bucket.

La chiave determina in quale bucket viene inserita un'entrata.
Il valore è ciò che si ottiene cercando la chiave.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Calcolare l'hash della chiave

Quando chiama put(key, value), la mappa chiama key.hashCode() per ottenere un int.

HashMap poi distribuisce questi bit con una funzione interna, in modo che anche hash code non ottimali si distribuiscano tra i bucket.

Il numero finale viene ridotto con hash & (table.length - 1) per ottenere l'indice del bucket.
La lunghezza della tabella è sempre una potenza di due, quindi la maschera funziona.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

I bucket in azione

Ogni bucket può contenere più di un'entrata. Quando due chiavi vengono associate allo stesso bucket, si verifica una collisione.

Le collisioni sono normali e previste. HashMap le gestisce concatenando le entrate all'interno del bucket.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Collisioni e concatenamento

Prima di Java 8, tutte le entrate in collisione risiedevano in una lista concatenata semplice all'interno del bucket.

La ricerca percorre la lista chiamando equals() finché non trova la chiave corrispondente.

Poche collisioni: il comportamento resta di fatto O(1).
Molte collisioni in un bucket: il costo tende a O(n) per quel bucket.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Perché FB ed Ea entrano in collisione

Le stringhe "FB" e "Ea" hanno lo stesso hashCode() in Java. Questo è un classico esempio di collisione.

Anche con hash code identici, la mappa le mantiene separate perché equals() le distingue all'interno del bucket.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Fattore di carico

Il fattore di carico controlla quanto si riempie la tabella prima di aumentare la propria capacità. Il valore predefinito è 0.75.

Una capacità di 16 e un fattore di carico di 0.75 fanno scattare il ridimensionamento a 12 entrate.
Un fattore di carico più basso spreca memoria, ma riduce le collisioni.
Un fattore di carico più alto risparmia memoria, ma aumenta le collisioni.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Ridimensionare la tabella

Quando il numero di entrate supera capacity * loadFactor, la tabella raddoppia le proprie dimensioni.

Ogni entrata esistente viene sottoposta nuovamente a re-hashing nella nuova tabella più grande. È un'operazione costosa, quindi preimpostare la capacità è importante per le mappe di grandi dimensioni.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Preimpostare la capacità per ottenere prestazioni migliori

Se sa approssimativamente quante entrate dovrà memorizzare, specifichi una capacità iniziale per evitare continui ridimensionamenti.

Regola pratica: capacità iniziale = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Chiavi e valori null

HashMap consente una chiave null e più valori null.

La chiave null viene sempre inserita nel bucket 0 (il suo hash viene considerato 0).
Usi getOrDefault per evitare ambiguità tra una chiave assente e un valore null.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

L'ordine di iterazione non è garantito

HashMap non offre alcuna garanzia sull'ordine di iterazione. L'ordine dipende dagli hash code e dalla disposizione dei bucket.

Se ha bisogno di un ordine prevedibile, usi LinkedHashMap (ordine di inserimento) o TreeMap (ordine ordinato).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Il percorso di get() in sintesi

Una ricerca segue questi passaggi:

Calcolare hashCode() e distribuire i bit.
Applicare una maschera per trovare l'indice del bucket.
Scorrere il bucket confrontando le chiavi con equals().
Restituire il valore corrispondente o null.

Un buon hashCode e un equals corretto rendono rapide tutte le fasi.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Verifica rapida

Verifichi la Sua comprensione di come HashMap trova un bucket.

Riepilogo

Ha imparato come funziona HashMap al suo interno:

Le chiavi vengono sottoposte ad hashing e assegnate ai bucket.
Le collisioni vengono gestite concatenando le entry in un bucket.
Il fattore di carico (0.75) attiva il raddoppiamento e il rehashing.
Il pre-dimensionamento evita costosi ridimensionamenti e l'ordine di iterazione non è garantito.

Successivamente vedrà perché hashCode da solo non è sufficiente senza un equals corretto.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Domande Frequenti

La lezione «Come funziona HashMap» è gratuita?

Sì — il testo completo di «Come funziona HashMap» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «Come funziona HashMap»?

Bucket, hashing e collisioni Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Come funziona HashMap»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a Java Academy