Memperkenalkan koleksi TreeMap

Suatu hari di universiti, saya perlu menulis kod untuk mengisih nama keluarga rakan sekelas saya, yang berfungsi sebagai kunci kepada data peribadi mereka, dalam tertib menaik. Saya menghabiskan banyak masa untuk perkara ini. Tetapi jika saya tahu tentang kelas TreeMap ketika itu, saya akan menyelesaikan tugas dengan lebih cepat.

Apakah TreeMap ? Ia ialah struktur data seperti kamus yang menyimpan elemen sebagai pasangan nilai kunci, menyusunnya mengikut kunci.

Di mana dan bagaimana ia boleh digunakan? Baiklah, ia sesuai untuk tugasan yang sama dengan nama keluarga rakan sekelas saya. Jika saya perlu menyimpan nilai dalam tertib menaik, bukannya menulis algoritma pengisihan saya sendiri, yang perlu saya lakukan ialah mencipta TreeMap dan meletakkan nilai di dalamnya.

Ia menyusun jenis seperti Integer dan String dalam tertib menaik. Tetapi jika anda ingin meletakkan jenis tersuai anda sendiri dalam TreeMap , maka kelas anda perlu melaksanakan antara muka Sebanding , supaya ia melaksanakan kaedah compareTo() , yang menunjukkan cara mengisih contoh 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 kaedah compareTo() supaya ia mengisih nilai mengikut nama pertama dalam susunan 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 susunan berikut:

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

Kelas TreeMap melaksanakan antara muka NavigableMap , yang seterusnya memanjangkan antara muka SortedMap . Ini membolehkan kelas TreeMap menggunakan pepohon untuk menyimpan nilai dalam susunan yang disusun.

Secara ringkasnya, pokok merah-hitam ialah struktur data yang menyimpan nilai dalam subpokok kanan jika lebih besar daripada akar, dan dalam subpokok kiri jika kurang. Pelaksanaan ini boleh mencari nilai dalam struktur dengan cepat.

Pokok merah-hitam mengimbangi diri, jadi ia mengubah strukturnya apabila setiap nilai baharu dimasukkan. Nilai tambah dahulu pada mulanya dianggap sebagai punca, tetapi nilai lain boleh menjadi punca semasa proses pengimbangan.

Nah, sekarang anda tahu apa itu TreeMap dan cara ia berfungsi.

Ingat bahawa TreeMap hanya boleh menyimpan objek yang kelasnya melaksanakan antara muka Sebanding dan mengatasi kaedah compareTo() .

Tetapi bagaimana jika kita menggunakan kelas pihak ketiga yang dimuatkan daripada pelbagai perpustakaan dan tidak boleh melaksanakan Sebanding di dalamnya? Terdapat penyelesaian untuk ini: tulis Comparator anda sendiri .

Comparator ialah antara muka yang mempunyai kaedah compare(). Kita boleh menggunakannya untuk membandingkan objek dan menyimpannya dalam 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 mencipta Comparator tersuai dan menyerahkan TreeMap kepada kelas.

Bermula dalam Java 8, kita boleh menulis ini menggunakan ungkapan lambda:

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

Dalam erti kata lain, untuk menyimpan nilai dalam TreeMap , anda perlu menentukan cara mengisih nilai tersebut. Terdapat dua cara untuk melakukan ini: melaksanakan Comparable atau melaksanakan Comparator anda sendiri .

Tetapi bagaimana jika kita perlu meletakkan null ke dalam TreeMap sebagai kunci? HashMap membolehkan anda melakukan ini. Ya, tetapi bagaimanakah TreeMap mengendalikan perkara ini?

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

Menjalankan kod ini memberi kita ralat:

Masalahnya ialah secara dalaman kelas TreeMap membandingkan nilai menggunakan kaedah compareTo() . Anda pastinya boleh memasukkan nilai nol dan kod itu akan disusun. Tetapi pada masa jalan anda akan mendapat ralat, kerana kaedah itu akan dipanggil pada nilai nol , menyebabkan NullPointerException dibuang.

Perbandingan HashMap dan TreeMap

Tidak seperti TreeMap , HashMap membenarkan anda menyimpan null sebagai kunci. Struktur mempunyai tempat khusus untuk semua kekunci null . HashMap dapat menyimpan kekunci nol kerana ia menentukan ke mana ia pergi berdasarkan nilai cincang mereka, dan pengiraan nilai cincang tidak memerlukan perbandingan. Jadi semua kunci null mempunyai tempatnya.

Itu sahaja — kini anda tahu apa yang perlu digunakan apabila anda perlu menyimpan nilai dalam tertib yang diisih, dan cara menetapkan peraturan untuk mengisih.