Java Academy · Pelajaran

Pohon dan Prestasi

Cara Java 8+ mengendalikan perlanggaran

Pelajaran 4 daripada 413 langkah

Pohon dan Prestasi ialah pelajaran Java Academy percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Java Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Masalah Perlanggaran

Sebelum Java 8, baket dengan banyak perlanggaran menjadi senarai terpaut yang panjang. Carian dalam baket itu merosot kepada O(n).

Penyerang boleh mengeksploitasi perkara ini dengan kunci yang direka khas untuk menyebabkan penafian perkhidmatan, dengan semuanya dicincang kepada satu baket.

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

Penukaran kepada Pokok dalam Java 8

Java 8 menambah penukaran kepada pokok. Apabila satu baket menyimpan terlalu banyak entri, senarai terpaut itu ditukar menjadi pokok merah-hitam yang seimbang.

Carian dalam baket itu kemudian menjadi O(log n) dan bukannya 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));
    }
}

Ambang: TREEIFY_THRESHOLD

Pemalar TREEIFY_THRESHOLD ialah 8. Baket ditukar kepada pokok apabila mencapai 8 entri.

Namun, terdapat syarat kedua: saiz jadual juga mestilah sekurang-kurangnya MIN_TREEIFY_CAPACITY (64); jika tidak, saiz peta diubah dan bukannya ditukar kepada pokok.

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

Ubah Saiz Dahulu, Tukar kepada Pokok Kemudian

Jika baket melimpah tetapi jadual masih kecil (kurang daripada 64), HashMap mengubah saiz jadual terlebih dahulu.

Perubahan saiz biasanya mengagihkan semula entri dan menghapuskan titik panas, jadi penukaran kepada pokok hanyalah pilihan terakhir untuk taburan hash yang benar-benar buruk.

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

Penukaran Kembali daripada Pokok

Pokok tidak kekal selama-lamanya. Jika pengalihan keluar mengecilkan baket hingga kurang daripada UNTREEIFY_THRESHOLD (6), pokok itu kembali menjadi senarai terpaut.

Jarak antara 8 (penukaran kepada pokok) dan 6 (penukaran kembali) mengelakkan perubahan berulang-alik pada sempadan.

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

Pokok Memerlukan Susunan Comparable atau Identiti

Pokok merah-hitam mesti menyusun entrinya. HashMap mula-mula membandingkan kod cincangan; jika seri, seri itu diputuskan oleh Comparable jika kunci melaksanakannya, atau sebaliknya melalui pemutus seri yang stabil berdasarkan nama kelas dan identiti.

Kunci yang Comparable (seperti String atau integer) memberikan susunan pokok yang paling kemas.

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

Kesan Praktikal

Untuk kebanyakan program sebenar yang mempunyai kod cincangan yang baik, Anda tidak akan pernah melihat penukaran kepada pokok. Baket kekal pendek.

Penukaran kepada pokok ialah jaring keselamatan yang mengehadkan carian kes terburuk kepada O(log n), walaupun pencincangan lemah atau dimanipulasi oleh penyerang.

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

hashCode Pemalar Memaksa Penukaran kepada Pokok

Jika Anda sengaja memulangkan hashCode pemalar, setiap kunci masuk ke satu baket. Dengan kapasiti 64 atau lebih, baket itu ditukar kepada pokok.

Ini menunjukkan jaring keselamatan tersebut, tetapi ia ialah petanda reka bentuk yang kurang baik. Sebaliknya, betulkan 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)));
    }
}

Kos Memori Pokok

Nod pokok lebih besar daripada nod senarai terpaut biasa kerana nod tersebut menyimpan rujukan kepada induk, kiri, kanan dan warna.

Inilah satu lagi sebab penukaran kepada pokok ialah pilihan sandaran, bukan lalai: pokok menukar memori dengan kelajuan kes terburuk.

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

Cara Mengelakkan Penukaran kepada Pokok

Anda hampir tidak pernah mahu bergantung pada penukaran kepada pokok. Elakkannya dengan:

Menulis hashCode() yang mempunyai taburan baik.
Menggunakan jenis terbina dalam atau rekod sebagai kunci.
Menetapkan saiz awal peta untuk mengurangkan perlanggaran.

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

Ringkasan Prestasi

Kos operasi HashMap:

hash yang baik: O(1) secara purata.
Baket terpaut: O(n) bagi setiap baket dalam kes terburuk.
Baket yang ditukar kepada pokok: O(log n) bagi setiap baket.

Penukaran kepada pokok mengehadkan kes terburuk, tetapi hashCode yang baik memastikan Anda kekal dalam lingkungan 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));
    }
}

Semakan Pantas

Uji pengetahuan Anda tentang penukaran kepada pokok.

Jawab dalam pelajaran interaktif

Rumusan

Anda telah mempelajari cara HashMap moden mengendalikan perlanggaran:

Baket ditukar kepada pokok pada 8 entri apabila kapasiti sekurang-kurangnya 64.
Pokok memberikan carian kes terburuk O(log n).
Baket kembali menjadi senarai apabila kurang daripada 6 entri.
hashCode yang baik bermakna Anda jarang mencetuskan jaring keselamatan ini.

Anda telah menamatkan kursus dalaman HashMap.

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

Percuma untuk bermula

Pelajari Java dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 104
Pelajaran: 374

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Pohon dan Prestasi” percuma?

Ya — teks penuh “Pohon dan Prestasi” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Java Academy, tingkat taraf kepada CoddyKit PRO. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Pohon dan Prestasi”?

Cara Java 8+ mengendalikan perlanggaran Anda berlatih Java Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Java Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Java Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Pohon dan Prestasi” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy