Memperkenalkan koleksi TreeMap

Suatu hari di universitas, saya perlu menulis kode untuk mengurutkan nama belakang teman sekelas saya, yang berfungsi sebagai kunci data pribadi mereka, dalam urutan menaik. Saya menghabiskan banyak waktu untuk ini. Tetapi jika saya tahu tentang kelas TreeMap saat itu, saya akan menyelesaikan tugas lebih cepat.

Apa itu Peta Pohon ? Ini adalah struktur data seperti kamus yang menyimpan elemen sebagai pasangan kunci-nilai, mengurutkannya berdasarkan kunci.

Di mana dan bagaimana itu bisa digunakan? Yah, itu akan ideal untuk tugas yang sama dengan nama belakang teman sekelasku. Jika saya perlu menyimpan nilai dalam urutan menaik, alih-alih menulis algoritme pengurutan saya sendiri, yang harus saya lakukan hanyalah membuat TreeMap dan memasukkan nilai ke dalamnya.

Ini mengurutkan tipe seperti Integer dan String dalam urutan menaik. Tetapi jika Anda ingin menempatkan tipe kustom Anda sendiri di TreeMap , maka kelas Anda perlu mengimplementasikan antarmuka Sebanding , sehingga mengimplementasikan metode compareTo() , yang menunjukkan cara mengurutkan instance kelas Anda.

public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Mari kita ganti metode compareTo() sehingga mengurutkan nilai berdasarkan nama depan dalam urutan abjad terbalik:

TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Nilai akan disimpan dalam urutan berikut:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

Kelas TreeMap mengimplementasikan antarmuka NavigableMap , yang pada gilirannya memperluas antarmuka SortedMap . Ini memungkinkan kelas TreeMap menggunakan pohon untuk menyimpan nilai dalam urutan terurut.

Sederhananya, pohon merah-hitam adalah struktur data yang menyimpan nilai di subpohon kanan jika lebih besar dari akar, dan di subpohon kiri jika lebih kecil. Implementasi ini dapat mencari nilai dalam struktur dengan sangat cepat.

Pohon merah-hitam menyeimbangkan dirinya sendiri, sehingga mengubah strukturnya saat setiap nilai baru disisipkan. Nilai tambah pertama kali dianggap sebagai akar, tetapi nilai lain dapat menjadi akar selama proses penyeimbangan.

Nah, sekarang kamu sudah tahu apa itu TreeMap dan cara kerjanya.

Ingat bahwa TreeMap hanya dapat menyimpan objek yang kelasnya mengimplementasikan antarmuka Sebanding dan mengganti metode compareTo() .

Tetapi bagaimana jika kita menggunakan class pihak ketiga yang diambil dari berbagai library dan tidak dapat mengimplementasikan Comparable di dalamnya? Ada solusi untuk ini: tulis Pembanding Anda sendiri .

Komparator adalah antarmuka yang memiliki metode bandingkan (). Kita bisa menggunakannya untuk membandingkan objek dan menyimpannya di TreeMap .

Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

Dalam contoh ini, kami membuat Comparator khusus dan meneruskan TreeMap ke kelas.

Mulai di Java 8, kita dapat menulis ini menggunakan ekspresi lambda:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

Dengan kata lain, untuk menyimpan nilai dalam TreeMap , Anda perlu menentukan cara mengurutkannya. Ada dua cara untuk melakukan ini: menerapkan Sebanding atau menerapkan Pembanding Anda sendiri .

Tetapi bagaimana jika kita perlu memasukkan null ke dalam TreeMap sebagai kunci? HashMap memungkinkan Anda melakukan ini. Ya, tapi bagaimana TreeMap menangani ini?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Menjalankan kode ini memberi kita kesalahan:

Masalahnya adalah secara internal kelas TreeMap membandingkan nilai menggunakan metode compareTo() . Anda pasti bisa memasukkan nilai nol dan kode akan dikompilasi. Tetapi pada saat runtime Anda akan mendapatkan error, karena metode ini akan dipanggil pada nilai null , menyebabkan NullPointerException dilempar.

Perbandingan HashMap dan TreeMap

Tidak seperti TreeMap , HashMap memungkinkan Anda menyimpan null sebagai kunci. Struktur memiliki tempat khusus untuk semua kunci nol . HashMap dapat menyimpan kunci nol karena menentukan ke mana mereka pergi berdasarkan nilai hash mereka, dan menghitung nilai hash tidak memerlukan perbandingan. Jadi semua kunci nol memiliki tempatnya.

Itu dia — sekarang Anda tahu apa yang harus digunakan saat Anda perlu menyimpan nilai dalam urutan terurut, dan cara mengatur aturan untuk menyortir.