TreeMap kolleksiyasi bilan tanishish

Universitetda bir kun bizga guruhdoshlarimning shaxsiy ishlari uchun kalitlar bo'lgan familiyalarni o'sish tartibida saralash vazifasini yozish kerak edi, va bu menga juda ko'p vaqt oldi. Ammo, agar o'sha paytda TreeMap klassi bilan tanishgan bo'lsam, buni ancha tezroq amalga oshirgan bo'lardim.

TreeMap nima? Bu kalit-qiymat ko'rinishida elementlarni saqlash imkonini beruvchi ma'lumotlar tuzilmasi bo'lib, kalitlar bo'yicha saralashni ta'minlaydi.

U qayerda va qanday ishlatilishi mumkin? Masalan, guruhdoshlarim bilan bir holatda. Agar menga qiymatlarni o'sish tartibida saqlash kerak bo'lsa, o'z saralash algoritmlarini yozish o'rniga, faqat TreeMap yaratib, qiymatlarni unga joylashtirish kifoya.

Integer va String kabi turlarga o'sish tartibida saralash tartibi qo'llanadi. Ammo agar siz o'z turini TreeMap ga joylashtirmoqchi bo'lsangiz, sizdan klassingiz Comparable interfeysini amalga oshirishi va compareTo() metodini implementatsiya qilgan bo'lishi kerak, va shu turdagi qiymatlar qanday saralanishi kerakligi ko'rsatilgan bo'lishi kerak.

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 + '\'' +
                '}';
    }
}

compareTo() metodini alfavitdan kamayish tartibda ismni saralash uchun qayta yozamiz:

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

Qiymatlar quyidagi tartibda saqlanadi:

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

TreeMap klassi NavigableMap interfeysini amalga oshiradi, bu esa o'z navbatida SortedMap ni kengaytiradi. Bu TreeMap klassiga daraxtlardan foydalanish va qiymatlarni saralangan holda saqlash imkonini beradi.

Oddiy so'zlar bilan aytganda, qizil-qora daraxt — bu ma'lumotlar tuzilmasi bo'lib, ildizdan katta qiymatlarni o'ngda, kichiklarini esa chapda saqlaydi. Bunday amalga oshirish tuzilmani tezroq qidirishga yordam beradi.

Qizil-qora daraxt o'z-o'zini muvozanatlaydi, shuning uchun har bir yangi qo'shilishda tuzilmasini o'zgartiradi, chunki yangi qiymatlar qo'shilmoqda. Ildiz qiymati birinchi bo'lib qo'shilgan qiymat hisoblanadi, ammo balanslash jarayonida, ildiz boshqa qiymatga ham aylanishi mumkin.

Endi sen TreeMap nima ekanligini va qaysi printsip asosida ishlashini bilasan.

Shuni eslayin, TreeMap da faqat Comparable interfeysini amalga oshirgan va compareTo() metodini qayta yozganlarni saqlashingiz mumkin.

Agar biz boshqa kutubxonalardan yuklayotgan chet el klasslaridan foydalansak va ular ichiga Comparable ni amalga oshira olmasak, nima qilish kerak? Bunday hollarda yechim bor: o'zingizning Comparator ni yozish.

Comparator — bu compare() metodi bor interfeys. Uning yordami bilan biz obyektlarni taqqoslashimiz va TreeMap da saqlashimiz mumkin.

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

Bu misolda biz maxsus Comparator yaratdik va TreeMap klassiga uzatdik.

Java 8 dan boshlab, bu lamsda ifoda yordamida yozilishi mumkin:

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

Demak, TreeMap da qiymatlarni saqlash uchun, ularni qanday saralashni ko‘rsatish kerak. Buni ikki usulda amalga oshirish mumkin: Comparable ni amalga oshirish yoki o'zingizning Comparator ni yaratish.

Agar TreeMap ga null qiymatini kalit qilib qo'yish zarur bo'lsa, nima qilish kerak? HashMap bunga imkon beradi. Ammo TreeMap bu bilan qanday ishlaydi?

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

Ushbu kodni ishga tushirganda, biz xatoni olamiz:

Muammo TreeMap klassi ichida qiymatlarni compareTo() metodi bilan taqqoslash amalga oshirilayotgani. Sen, albatta, null qiymatini qo'yish mumkin va u kompilyatsiya qilinadi, ammo ishlash vaqtida siz xatoni olasiz, chunki null qiymatidagi metod chaqiriladi va NullPointerException chiqadi.

HashMap va TreeMap taqqoslanishi

TreeMap ga nisbatan, HashMap da null kalit sifatida saqlashga ruxsat etiladi. Barcha null kalitlari uchun tuzilishda alohida joy ajratilgan. null kalitlarni HashMap da saqlashga imkon beradigan narsa — bu joyni aniqlash hesh qiymati bo'yicha amalga oshirilishi va buning uchun qiymatlarni boshqa qiymatlar bilan taqqoslash kerak emas. Shu sababli barcha null kalitlarning alohida joyi mavjud.

Endi sen bilasan, saralangan holda qiymatlarni saqlash zarur bo'lganda nimadan foydalanish kerakligini va saralash qoidalari va tartibini qanday belgilashni.