Java Academy · leksjon

Treeification og ytelse

Slik håndterer Java 8+ kollisjoner

Leksjon 4 av 413 trinn

Treeification og ytelse er en gratis leksjon i Java Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Java Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Java Academy inneholder totalt 4 leksjoner.

Kollisjonsproblemet

Før Java 8 ble en bøtte med mange kollisjoner til en lang lenket liste. Oppslag i denne bøtten ble redusert til O(n).

En angriper kunne utnytte dette med spesiallagde nøkler for å forårsake et tjenestenektangrep ved å få alle til å hashe til én bøtte.

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

Treeification i Java 8

Java 8 introduserte treeification. Når én bøtte inneholder for mange oppføringer, konverteres den lenkede listen til et balansert rød-svart-tre.

Oppslag i denne bøtten blir da O(log n) i stedet for 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));
    }
}

Grensen: TREEIFY_THRESHOLD

Konstanten TREEIFY_THRESHOLD er 8. En bøtte konverteres til et tre når den når 8 oppføringer.

Men det finnes et annet vilkår: tabellen må også være minst MIN_TREEIFY_CAPACITY (64) stor, ellers endrer mapet størrelse i stedet.

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

Endre størrelse først, treeify senere

Hvis en bøtte renner over, men tabellen fortsatt er liten (under 64), endrer HashMap først størrelsen på tabellen.

Endring av størrelse omfordeler vanligvis oppføringene og fjerner flaskehalsen, så treeification er bare siste utvei når hashfordelingen faktisk er dårlig.

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

Untreeification

Trær er ikke permanente. Hvis slettinger gjør en bøtte mindre enn UNTREEIFY_THRESHOLD (6), går treet tilbake til en lenket liste.

Avstanden mellom 8 (treeify) og 6 (untreeify) hindrer at strukturen veksler frem og tilbake ved grensen.

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ær trenger Comparable eller identitetsrekkefølge

Et rød-svart-tre må sortere oppføringene. HashMap sammenligner først hashkoder; ved likhet avgjøres rekkefølgen av Comparable hvis nøklene implementerer det, ellers av en stabil tie-break basert på klassenavn og identitet.

Nøkler som er Comparable (som String eller Integer) gir den ryddigste treordenen.

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 betydning

For de fleste virkelige programmer med gode hashkoder vil De aldri se treeification. Bøttene forblir korte.

Treeification er et sikkerhetsnett som begrenser oppslag i verste fall til O(log n), selv når hashing er dårlig eller ondsinnet.

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 tvinger frem trær

Hvis De med vilje returnerer en konstant hashCode, havner hver nøkkel i én bøtte. Med kapasitet på minst 64 blir denne bøtten konvertert til et tre.

Dette demonstrerer sikkerhetsnettet, men det er et dårlig designvalg. Rett heller 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)));
    }
}

Minn kostnad for trær

Trenoder er større enn vanlige noder i lenkede lister fordi de lagrer referanser til forelder, venstre, høyre og farge.

Dette er en annen grunn til at treeification er en reserveordning og ikke standarden: trær bytter minne mot hastighet i verste 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");
    }
}

Slik unngår De treeification

De vil nesten aldri være avhengige av treeification. Unngå det ved å:

Skrive en hashCode() med god fordeling.
Bruke innebygde typer eller records som nøkler.
Forhåndsdimensjonere mapet for å redusere kollisjoner.

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

Ytelsesoppsummering

Kostnader for operasjoner i HashMap:

God hash: O(1) i gjennomsnitt.
Lenket bøtte: O(n) per bøtte i verste fall.
Bøtte som er konvertert til et tre: O(log n) per bøtte.

Treeification begrenser verste fall, men en god hashCode holder oppslagene 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));
    }
}

Kort test

Test kunnskapene Deres om treeification.

Besvar den i den interaktive leksjonen

Oppsummering

De har lært hvordan moderne HashMap håndterer kollisjoner:

Bøtter konverteres til trær ved 8 oppføringer når kapasiteten er minst 64.
Trær gir oppslag i verste fall på O(log n).
Bøtter konverteres tilbake fra trær under 6 oppføringer.
En god hashCode betyr at De sjelden utløser dette sikkerhetsnettet.

De har fullført kurset om HashMap-interne detaljer.

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

Gratis å komme i gang

Lær deg Java med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 104
Leksjoner: 374

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Treeification og ytelse» gratis?

Ja – hele teksten i «Treeification og ytelse» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Java Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Java Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Treeification og ytelse»?

Slik håndterer Java 8+ kollisjoner Du øver på Java Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Java Academy?

Ingen tidligere erfaring er nødvendig. Java Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Treeification og ytelse»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Java Academy-leksjonen?

Ja. Alle Java Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Java Academy