Java Academy · Oppitunti

Puumaistaminen ja suorituskyky

Näin Java 8+ käsittelee törmäyksiä.

Oppitunti 4/413 vaihetta

Puumaistaminen ja suorituskyky on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.

Törmäysongelma

Ennen Java 8:aa paljon törmäyksiä sisältävästä lokerosta tuli pitkä linkitetty lista. Tällaisen lokeron haku hidastui muotoon O(n).

Hyökkääjä saattoi hyödyntää tätä muodostamalla tarkoituksellisia avaimia, jotka kaikki hajautuivat samaan lokeroon ja aiheuttivat palvelunestohyökkäyksen.

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

Puun muodostaminen Java 8:ssa

Java 8 lisäsi puuksi muuttamisen. Kun yksittäisessä lokerossa on liikaa tietueita, linkitetty lista muutetaan tasapainotetuksi punamustaksi puuksi.

Tällöin haku kyseisestä lokerosta muuttuu muotoon O(log n) aiemman O(n):n sijaan.

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

Kynnysarvo: TREEIFY_THRESHOLD

Vakion TREEIFY_THRESHOLD arvo on 8. Lokero muutetaan puuksi, kun siinä on 8 tietuetta.

Lisäksi on täytyttävä toinen ehto: taulukon koon on oltava vähintään MIN_TREEIFY_CAPACITY (64), muuten mapin kokoa kasvatetaan.

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

Kokoa kasvatetaan ensin, puu muodostetaan myöhemmin

Jos lokero täyttyy yli, mutta taulukko on vielä pieni (alle 64), HashMap kasvattaa taulukon kokoa ensin.

Koon kasvattaminen yleensä jakaa tietueet uudelleen ja poistaa keskittymän, joten puuksi muuttaminen on viimeinen keino aidosti huonosti jakautuville hajautusarvoille.

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

Puun muuttaminen takaisin listaksi

Puut eivät ole pysyviä. Jos poistot pienentävät lokeron koon alle arvon UNTREEIFY_THRESHOLD (6), puu muuttuu takaisin linkitetyksi listaksi.

Raja-arvojen 8 (puuksi muuttaminen) ja 6 (listaksi muuttaminen) välinen ero estää jatkuvan vaihtelun rajan tuntumassa.

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

Puut tarvitsevat Comparable- tai identiteettijärjestyksen

Punamustan puun on järjestettävä tietueensa. HashMap vertaa ensin hajautusarvoja. Tasatilanteessa se käyttää Comparable-rajapintaa, jos avaimet toteuttavat sen, ja muussa tapauksessa luokan nimien ja identiteetin perusteella muodostettua vakaata tasoitusta.

Comparable-rajapinnan toteuttavat avaimet, kuten String tai Integer, tuottavat selkeimmän puujärjestyksen.

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

Käytännön vaikutus

Useimmissa oikeissa ohjelmissa, joissa hajautusarvot ovat riittävän hyviä, ette koskaan näe puuksi muuttamista. Lokerot pysyvät lyhyinä.

Puuksi muuttaminen on turvaverkko, joka rajoittaa pahimman tapauksen haun muotoon O(log n), vaikka hajautus olisi huonoa tai vastustajan tarkoituksella aiheuttamaa.

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

Vakioarvoinen hashCode pakottaa puut käyttöön

Jos palautatte tarkoituksella vakioarvon hashCode-metodista, kaikki avaimet päätyvät samaan lokeroon. Kun kapasiteetti on vähintään 64, lokero muutetaan puuksi.

Tämä havainnollistaa turvaverkkoa, mutta kyseessä on suunnitteluvirhe. Korjatkaa sen sijaan 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)));
    }
}

Puiden muistinkulutus

Puusolmut ovat suurempia kuin tavalliset linkitetyn listan solmut, koska ne tallentavat viitteet isäntään, vasempaan ja oikeaan lapseen sekä väriin.

Tämä on toinen syy siihen, että puuksi muuttaminen on vararatkaisu eikä oletus: puut vaihtavat muistia pahimman tapauksen nopeuteen.

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

Puun muodostamisen välttäminen

Puun muodostamiseen ei lähes koskaan kannata luottaa. Välttäkää sitä seuraavasti:

Kirjoittakaa hyvin jakautuva hashCode().
Käyttäkää avaimina sisäänrakennettuja tyyppejä tai recordeja.
Määrittäkää mapille ennakkokoko törmäysten vähentämiseksi.

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

Suorituskyvyn yhteenveto

HashMap-operaatioiden kustannukset:

Hyvä hajautusarvo: keskimäärin O(1).
Linkitetty lokero: pahimmassa tapauksessa O(n) lokerokohtaisesti.
Puuksi muutettu lokero: O(log n) lokerokohtaisesti.

Puuksi muuttaminen rajoittaa pahinta tapausta, mutta hyvä hashCode pitää suorituksen O(1)-tasolla.

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

Pikainen tarkistus

Testatkaa tietonne puuksi muuttamisesta.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Opitte, miten nykyaikainen HashMap käsittelee törmäyksiä:

Lokerot muuttuvat puiksi, kun niissä on 8 tietuetta ja kapasiteetti on vähintään 64.
Puut takaavat haun pahimman tapauksen ajaksi O(log n).
Lokerot muuttuvat takaisin listoiksi, kun niissä on alle 6 tietuetta.
Hyvä hashCode tarkoittaa, että tätä turvaverkkoa tarvitaan harvoin.

Olette suorittaneet HashMapin sisäisen toiminnan kurssin.

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

Aloita maksutta

Opi Java tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 104
Oppitunnit: 374

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Puumaistaminen ja suorituskyky” ilmainen?

Kyllä – oppitunnin ”Puumaistaminen ja suorituskyky” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Puumaistaminen ja suorituskyky”?

Näin Java 8+ käsittelee törmäyksiä. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Puumaistaminen ja suorituskyky”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?

Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Java Academy