Java Academy · Pelajaran

Treeification dan Performa

Cara Java 8+ menangani collision.

Pelajaran 4 dari 413 langkah

Treeification dan Performa adalah pelajaran Java Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Java Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Java Academy mencakup 4 pelajaran total.

Masalah Tabrakan

Sebelum Java 8, keranjang dengan banyak tabrakan menjadi daftar berantai yang panjang. Pencarian dalam keranjang tersebut menurun menjadi O(n).

Penyerang dapat mengeksploitasi hal ini dengan kunci yang dirancang khusus untuk menyebabkan penolakan layanan, karena semuanya menghasilkan hash ke satu keranjang.

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

Pembentukan Pohon pada Java 8

Java 8 menambahkan pembentukan pohon. Saat sebuah keranjang menampung terlalu banyak entri, daftar berantai diubah menjadi pohon merah-hitam yang seimbang.

Pencarian dalam keranjang tersebut kemudian menjadi O(log n), bukan 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 Batas: TREEIFY_THRESHOLD

Konstanta TREEIFY_THRESHOLD bernilai 8. Keranjang diubah menjadi pohon saat mencapai 8 entri.

Namun, ada kondisi kedua: ukuran tabel juga harus setidaknya MIN_TREEIFY_CAPACITY (64); jika tidak, peta akan mengubah ukurannya.

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 Ukuran Dahulu, Bentuk Pohon Kemudian

Jika sebuah keranjang meluap tetapi tabel masih kecil (kurang dari 64), HashMap akan mengubah ukuran tabel terlebih dahulu.

Perubahan ukuran biasanya mendistribusikan ulang entri dan menghilangkan titik padat, sehingga pembentukan pohon hanya menjadi pilihan terakhir untuk distribusi 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());
    }
}

Mengembalikan Pohon Menjadi Daftar

Pohon tidak bersifat permanen. Jika penghapusan mengurangi isi keranjang hingga di bawah UNTREEIFY_THRESHOLD (6), pohon dikembalikan menjadi daftar berantai.

Jarak antara 8 (pembentukan pohon) dan 6 (pengembalian menjadi daftar) mencegah perubahan berulang antara keduanya di sekitar batas.

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

Pohon Memerlukan Urutan Comparable atau Identitas

Pohon merah-hitam harus mengurutkan entrinya. HashMap pertama-tama membandingkan kode hash; jika sama, perbandingan ditentukan oleh Comparable jika kunci mengimplementasikannya, atau oleh pemecah seri yang stabil berdasarkan nama kelas dan identitas.

Kunci yang bersifat Comparable (seperti String atau bilangan bulat) menghasilkan urutan pohon yang paling rapi.

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

Dampak Praktis

Untuk sebagian besar program nyata dengan kode hash yang baik, Anda tidak akan pernah melihat pembentukan pohon. Keranjang tetap pendek.

Pembentukan pohon adalah pengaman yang membatasi pencarian terburuk pada O(log n), bahkan saat penghashan buruk atau dilakukan secara berbahaya.

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 Konstan Memaksa Pembentukan Pohon

Jika Anda sengaja mengembalikan hashCode konstan, setiap kunci masuk ke satu keranjang. Dengan kapasitas 64 atau lebih, keranjang tersebut akan diubah menjadi pohon.

Hal ini menunjukkan fungsi pengaman tersebut, tetapi merupakan indikasi desain yang buruk. Sebaiknya perbaiki 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)));
    }
}

Biaya Memori Pohon

Simpul pohon berukuran lebih besar daripada simpul daftar berantai biasa karena menyimpan referensi ke induk, kiri, kanan, dan warna.

Inilah alasan lain pembentukan pohon menjadi pilihan cadangan, bukan bawaan: pohon menukar memori dengan kecepatan terburuk yang lebih baik.

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 Menghindari Pembentukan Pohon

Anda hampir tidak pernah ingin bergantung pada pembentukan pohon. Hindarilah dengan cara:

Menulis hashCode() yang terdistribusi dengan baik.
Menggunakan tipe bawaan atau record sebagai kunci.
Menentukan ukuran awal peta untuk mengurangi tabrakan.

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 Kinerja

Biaya operasi HashMap:

Hash yang baik: O(1) rata-rata.
Keranjang berantai: O(n) per keranjang dalam kasus terburuk.
Keranjang berbentuk pohon: O(log n) per keranjang.

Pembentukan pohon membatasi kasus terburuk, tetapi hashCode yang baik membuat Anda tetap berada pada 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));
    }
}

Pemeriksaan Singkat

Uji pengetahuan Anda tentang pembentukan pohon.

Jawab di pelajaran interaktif

Rangkuman

Anda telah mempelajari cara HashMap modern menangani tabrakan:

Keranjang dibentuk menjadi pohon pada 8 entri saat kapasitas setidaknya 64.
Pohon memberikan pencarian terburuk sebesar O(log n).
Keranjang dikembalikan menjadi daftar jika jumlah entrinya kurang dari 6.
hashCode yang baik berarti Anda jarang mengaktifkan pengaman ini.

Anda telah menyelesaikan kursus internal HashMap.

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

Gratis untuk memulai

Belajar Java dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus: 104
Pelajaran: 374

Mulai belajar gratis Lihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Treeification dan Performa” gratis?

Ya — teks lengkap “Treeification dan Performa” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Java Academy, upgrade ke CoddyKit PRO. Kursus Java Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Treeification dan Performa”?

Cara Java 8+ menangani collision. Kamu berlatih Java Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Java Academy?

Tidak diperlukan pengalaman sebelumnya. Java Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Treeification dan Performa” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Java Academy