Java Academy · Lezione

Treeification e prestazioni

Come Java 8+ gestisce le collisioni

Treeification e prestazioni è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 4 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.

Il problema delle collisioni

Prima di Java 8, un bucket con molte collisioni diventava una lunga lista concatenata. La ricerca in quel bucket degenerava in O(n).

Un attaccante poteva sfruttare questa situazione con chiavi appositamente create per causare una negazione del servizio, facendo sì che tutti gli hash finissero in un unico bucket.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

La conversione in albero di Java 8

Java 8 ha introdotto la conversione in albero. Quando un singolo bucket contiene troppe entry, la lista concatenata viene convertita in un albero rosso-nero.

La ricerca in quel bucket diventa quindi O(log n) anziché O(n).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

La soglia: TREEIFY_THRESHOLD

La costante TREEIFY_THRESHOLD vale 8. Un bucket viene convertito in un albero quando raggiunge 8 entry.

Esiste però una seconda condizione: la tabella deve avere una capacità di almeno MIN_TREEIFY_CAPACITY (64); altrimenti la mappa viene ridimensionata.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Prima ridimensionare, poi convertire in albero

Se un bucket supera il limite ma la tabella è ancora piccola (meno di 64), HashMap ridimensiona prima la tabella.

Il ridimensionamento di solito ridistribuisce le entry ed elimina il punto critico, quindi la conversione in albero è solo l'ultima risorsa per distribuzioni dell'hash realmente problematiche.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Riconversione in lista

Gli alberi non sono permanenti. Se le rimozioni riducono un bucket al di sotto di UNTREEIFY_THRESHOLD (6), l'albero torna a essere una lista concatenata.

La distanza tra 8 (conversione in albero) e 6 (riconversione in lista) evita continui passaggi avanti e indietro al confine della soglia.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Gli alberi richiedono un ordine Comparable o basato sull'identità

Un albero rosso-nero deve ordinare le proprie entry. HashMap confronta innanzitutto i codici hash; in caso di parità, usa Comparable se le chiavi lo implementano, altrimenti applica un criterio di spareggio stabile basato sui nomi delle classi e sull'identità.

Le chiavi Comparable (come String o Integer) garantiscono l'ordinamento più chiaro dell'albero.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Impatto pratico

Nella maggior parte dei programmi reali con buoni codici hash, non vedrà mai la conversione in albero. I bucket rimangono brevi.

La conversione in albero è una rete di sicurezza che limita la ricerca nel caso peggiore a O(log n), anche quando l'hashing è scadente o intenzionalmente ostile.

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("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Un hashCode costante forza la conversione in alberi

Se restituisce deliberatamente un hashCode costante, tutte le chiavi finiscono nello stesso bucket. Con una capacità di almeno 64, quel bucket viene convertito in un albero.

Questo dimostra il funzionamento della rete di sicurezza, ma indica una scelta progettuale discutibile. Corregga invece hashCode.

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

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Il costo in memoria degli alberi

I nodi degli alberi sono più grandi dei semplici nodi delle liste concatenate, perché memorizzano riferimenti al nodo padre, ai nodi sinistro e destro e al colore.

Questo è un altro motivo per cui la conversione in albero è una soluzione di ripiego, non quella predefinita: gli alberi scambiano memoria con prestazioni migliori nel caso peggiore.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

Come evitare la conversione in albero

Quasi mai vorrà affidarsi alla conversione in albero. La eviti:

Scrivendo un hashCode() ben distribuito.
Usando tipi integrati o record come chiavi.
Pre-dimensionando la mappa per ridurre le collisioni.

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

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Riepilogo delle prestazioni

Costo delle operazioni di HashMap:

Hash valido: O(1) in media.
Bucket concatenato: O(n) per bucket nel caso peggiore.
Bucket convertito in albero: O(log n) per bucket.

La conversione in albero limita il caso peggiore, ma un buon hashCode mantiene le prestazioni nell'ordine O(1).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Verifica rapida

Verifichi le Sue conoscenze sulla conversione in alberi.

Riepilogo

Ha imparato come HashMap gestisce oggi le collisioni:

I bucket vengono convertiti in alberi a 8 entry quando la capacità è almeno 64.
Gli alberi garantiscono una ricerca nel caso peggiore pari a O(log n).
I bucket vengono riconvertiti in liste al di sotto di 6 entry.
Un buon hashCode fa sì che questa rete di sicurezza venga attivata raramente.

Ha completato il corso sul funzionamento interno di HashMap.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Domande Frequenti

La lezione «Treeification e prestazioni» è gratuita?

Sì — il testo completo di «Treeification e prestazioni» è 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 «Treeification e prestazioni»?

Come Java 8+ gestisce le 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 4 di 4.

Quanto tempo richiede la lezione «Treeification e prestazioni»?

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