Java Academy · Lektion

Trädbildning och prestanda

Så hanterar Java 8+ kollisioner.

Lektion 4 av 413 steg

Trädbildning och prestanda är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Kollisionsproblemet

Före Java 8 blev en bucket med många kollisioner en lång länkad lista. Sökning i den bucketen försämrades till O(n).

En angripare kunde utnyttja detta med specialkonstruerade nycklar för att orsaka en överbelastningsattack, där alla hashades till samma 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());
    }
}

Trädbildning i Java 8

Java 8 införde treeification. När en enskild bucket innehåller för många poster omvandlas den länkade listan till ett balanserat rödsvart träd.

Sökning i den bucketen blir då O(log n) i stället för 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));
    }
}

Tröskeln: TREEIFY_THRESHOLD

Konstanten TREEIFY_THRESHOLD är 8. En bucket omvandlas till ett träd när den når 8 poster.

Men det finns ett andra villkor: tabellen måste också vara minst MIN_TREEIFY_CAPACITY (64) stor, annars ändrar mappen storlek i stället.

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);
    }
}

Ändra storleken först, skapa träd senare

Om en bucket blir överfull medan tabellen fortfarande är liten (under 64) ändrar HashMap först tabellens storlek.

En storleksändring omfördelar vanligtvis posterna och tar bort flaskhalsen, så treeification används bara som sista utväg vid genuint dålig hashfördelning.

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());
    }
}

Omvandling från träd

Träd är inte permanenta. Om borttagningar minskar en bucket till under UNTREEIFY_THRESHOLD (6) omvandlas trädet tillbaka till en länkad lista.

Skillnaden mellan 8 (treeify) och 6 (untreeify) förhindrar att strukturen växlar fram och tillbaka vid gränsen.

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");
    }
}

Träd behöver Comparable eller identitetsordning

Ett rödsvart träd måste kunna ordna sina poster. HashMap jämför först hashkoderna; vid lika hashkoder avgör Comparable ordningen om nycklarna implementerar det, annars används en stabil skiljemetod baserad på klassnamn och identitet.

Nycklar som är Comparable (till exempel String eller Integer) ger den tydligaste trädordningen.

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));
    }
}

Praktisk betydelse

I de flesta verkliga program med bra hashkoder kommer du aldrig att se treeification. Buckets förblir korta.

Treeification är ett skyddsnät som begränsar sökningens värsta fall till O(log n), även när hashningen är dålig eller avsiktligt manipulerad.

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"));
    }
}

En konstant hashCode tvingar fram träd

Om du medvetet returnerar en konstant hashCode hamnar varje nyckel i samma bucket. När kapaciteten är 64 eller större omvandlas den bucketen till ett träd.

Detta visar skyddsnätet, men är ett tecken på en dålig design. Åtgärda hashCode i stället.

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)));
    }
}

Minneskostnaden för träd

Trädnoder är större än vanliga noder i länkade listor eftersom de lagrar referenser till förälder, vänster, höger och färg.

Detta är ytterligare en anledning till att treeification är en reservlösning och inte standard: träd byter minne mot bättre prestanda i värsta fall.

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");
    }
}

Så undviker du treeification

Du vill nästan aldrig förlita dig på treeification. Undvik det genom att:

Skriva en välfördelad hashCode().
Använda inbyggda typer eller records som nycklar.
Ange en lämplig initial storlek på mappen för att minska antalet kollisioner.

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)));
    }
}

Prestandasammanfattning

Kostnader för HashMap-operationer:

Bra hashkod: O(1) i genomsnitt.
Länkad bucket: O(n) per bucket i värsta fall.
Bucket som omvandlats till träd: O(log n) per bucket.

Treeification begränsar värsta fallet, men en bra hashCode håller dig på O(1)-nivå.

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));
    }
}

Snabbkontroll

Testa dina kunskaper om treeification.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Du har lärt dig hur moderna HashMap hanterar kollisioner:

Buckets omvandlas till träd vid 8 poster när kapaciteten är minst 64.
Träd ger sökning med O(log n) i värsta fall.
Buckets omvandlas från träd när de innehåller färre än 6 poster.
En bra hashCode innebär att du sällan utlöser detta skyddsnät.

Du har slutfört kursen om HashMap-interner.

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

Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 104
Lektioner: 374

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Trädbildning och prestanda” gratis?

Ja – hela texten till ”Trädbildning och prestanda” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Trädbildning och prestanda”?

Så hanterar Java 8+ kollisioner. Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.

Hur lång tid tar lektionen ”Trädbildning och prestanda”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Java Academy