0Pricing
Java Academy · Lekcja

Konwersja do drzewa i wydajność

Jak Java 8+ obsługuje kolizje

Konwersja do drzewa i wydajność to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Problem kolizji

Przed Java 8 kubełek z wieloma kolizjami stawał się długą listą wiązaną. Wyszukiwanie w takim kubełku miało złożoność O(n).

Atakujący mógł to wykorzystać za pomocą specjalnie spreparowanych kluczy, powodując odmowę usługi, gdy wszystkie trafiały do jednego kubełka.

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

Przekształcanie w drzewo w Java 8

Java 8 wprowadziła przekształcanie w drzewo. Gdy pojedynczy kubełek zawiera zbyt wiele wpisów, lista wiązana jest zamieniana na zrównoważone czerwono-czarne drzewo.

Wyszukiwanie w takim kubełku ma wtedy złożoność O(log n) zamiast 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));
    }
}

Próg: TREEIFY_THRESHOLD

Stała TREEIFY_THRESHOLD ma wartość 8. Kubełek jest przekształcany w drzewo po osiągnięciu 8 wpisów.

Istnieje jednak drugi warunek: tablica musi mieć również pojemność co najmniej MIN_TREEIFY_CAPACITY (64), w przeciwnym razie mapa zostanie najpierw powiększona.

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

Najpierw powiększanie, potem drzewo

Jeśli kubełek się przepełni, ale tablica jest nadal mała (ma mniej niż 64 elementy), HashMap najpierw powiększa tablicę.

Powiększenie zwykle ponownie rozdziela wpisy i usuwa skupisko kolizji, dlatego przekształcanie w drzewo jest ostatecznością stosowaną przy rzeczywiście złym rozkładzie kodów skrótu.

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

Powrót z drzewa do listy

Drzewa nie są trwałe. Jeśli usuwanie elementów zmniejszy kubełek poniżej UNTREEIFY_THRESHOLD (6), drzewo jest ponownie zamieniane na listę wiązaną.

Różnica między 8 (przekształcenie w drzewo) a 6 (powrót do listy) zapobiega ciągłemu przełączaniu się na granicy.

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

Drzewa wymagają porządku Comparable lub tożsamości

Czerwono-czarne drzewo musi uporządkować swoje wpisy. HashMap najpierw porównuje kody skrótu; remisy rozstrzyga za pomocą Comparable, jeśli klucze implementują ten interfejs, a w przeciwnym razie za pomocą stabilnego kryterium opartego na nazwach klas i tożsamości obiektów.

Klucze implementujące Comparable, takie jak String lub Integer, zapewniają najczytelniejsze uporządkowanie drzewa.

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

Znaczenie praktyczne

W większości rzeczywistych programów z przyzwoitymi kodami skrótu nigdy nie zobaczą Państwo przekształcania w drzewo. Kubełki pozostają krótkie.

Przekształcanie w drzewo to mechanizm bezpieczeństwa, który ogranicza najgorszy przypadek wyszukiwania do O(log n), nawet gdy haszowanie jest słabe lub celowo utrudniane.

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

Stały hashCode wymusza drzewa

Jeśli celowo zwracany jest stały hashCode, każdy klucz trafia do jednego kubełka. Przy pojemności 64+ ten kubełek zostaje przekształcony w drzewo.

Pokazuje to działanie mechanizmu bezpieczeństwa, ale jest sygnałem złego projektu. Należy zamiast tego poprawić 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)));
    }
}

Koszt pamięci drzew

Węzły drzewa są większe niż zwykłe węzły listy wiązanej, ponieważ przechowują referencje do rodzica, lewego i prawego dziecka oraz koloru.

To kolejny powód, dla którego przekształcanie w drzewo jest rozwiązaniem awaryjnym, a nie domyślnym: drzewa wymieniają pamięć na szybkość w najgorszym przypadku.

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

Jak uniknąć przekształcania w drzewo

Niemal nigdy nie należy polegać na przekształcaniu w drzewo. Można go uniknąć przez:

  • Pisanie dobrze rozpraszającego hashCode().
  • Używanie typów wbudowanych lub rekordów jako kluczy.
  • Wstępne określenie rozmiaru mapy w celu ograniczenia kolizji.
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)));
    }
}

Podsumowanie wydajności

Koszt operacji HashMap:

  • Dobry kod skrótu: średnio O(1).
  • Kubełek z listą: w najgorszym przypadku O(n) na kubełek.
  • Kubełek przekształcony w drzewo: O(log n) na kubełek.

Przekształcanie w drzewo ogranicza najgorszy przypadek, ale dobry hashCode pozwala zachować złożoność 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));
    }
}

Szybkie sprawdzenie

Proszę sprawdzić swoją wiedzę o przekształcaniu w drzewo.

Podsumowanie

Poznali Państwo sposób, w jaki współczesny HashMap obsługuje kolizje:

  • Kubełki są przekształcane w drzewa po osiągnięciu 8 wpisów, jeśli pojemność wynosi co najmniej 64.
  • Drzewa zapewniają wyszukiwanie w najgorszym przypadku o złożoności O(log n).
  • Kubełki wracają do postaci listy poniżej 6 wpisów.
  • Dobry hashCode oznacza, że ten mechanizm bezpieczeństwa jest uruchamiany bardzo rzadko.

Ukończyli Państwo kurs dotyczący wewnętrznego działania HashMap.

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

Często zadawane pytania

Czy lekcja „Konwersja do drzewa i wydajność” jest bezpłatna?

Tak — pełny tekst „Konwersja do drzewa i wydajność” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Konwersja do drzewa i wydajność”?

Jak Java 8+ obsługuje kolizje Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Konwersja do drzewa i wydajność”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Jak działa HashMap
  2. Kontrakt equals/hashCode
  3. Implementowanie hashCode
  4. Konwersja do drzewa i wydajność
← Powrót do Java Academy