Представяме ви колекцията TreeMap

Един ден в университета трябваше да напиша code, който да сортира фамилните имена на съучениците ми, които служеха като ключове към техните лични данни, във възходящ ред. Прекарах много време в това. Но ако знаех за класа TreeMap тогава, щях да свърша задачата много по-бързо.

Какво е TreeMap ? Това е подобна на речник структура от данни, която съхранява елементи като двойки ключ-стойност, като ги сортира по ключ.

Къде и How може да се използва? Е, щеше да е идеално за същата задача с фамorите на съучениците ми. Ако трябва да съхранявам стойности във възходящ ред, instead of да пиша собствен алгоритъм за сортиране, всичко, което трябва да направя, е да създам TreeMap и да поставя стойностите в него.

Той сортира типове като Integer и String във възходящ ред. Но ако искате да поставите свой собствен персонализиран тип в TreeMap , тогава вашият клас трябва да имплементира интерфейса Comparable , така че да имплементира метода compareTo() , който показва How да сортирате екземпляри от вашия клас.

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() , така че да сортира стойностите по първо име в обратен азбучен ред:

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

Стойностите ще бъдат съхранени в следния ред:

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

Класът TreeMap имплементира интерфейса NavigableMap , който от своя страна разширява интерфейса SortedMap . Това позволява на класа TreeMap да използва дървета за съхраняване на стойности в сортиран ред.

Казано с прости думи, червено-черно дърво е структура от данни, която съхранява стойности в дясното поддърво, ако са по-големи от корена, и в лявото поддърво, ако са по-малки. Тази реализация може да търси стойности в структурата много бързо.

Червено-черното дърво се самобалансира, така че променя структурата си при всяка нова стойност. Първоначално добавената стойност се счита за основна, но друга стойност може да стане основна по време на процеса на балансиране.

Е, сега знаете Howво е TreeMap и How работи.

Не забравяйте, че TreeMap може да съхранява само обекти, чийто клас имплементира интерфейса Comparable и замества метода compareTo() .

Но Howво ще стане, ако използваме класове на трети страни, заредени от различни библиотеки и не можем да внедрим Comparable в тях? Има решение за това: напишете свой собствен Comparator .

Comparator е интерфейс, който има метод compare(). Можем да го използваме, за да сравняваме обекти и да ги съхраняваме в 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);

В този пример създадохме персонализиран Comparator и предадохме TreeMap на класа.

Започвайки от Java 8, можем да напишем това с помощта на ламбда израз:

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

С други думи, за да съхранявате стойности в TreeMap , трябва да укажете How да ги сортирате. Има два начина да направите това: внедрите Comparable or внедрите свой собствен Comparator .

Но Howво ще стане, ако трябва да поставим null в TreeMap като ключ? HashMap ви позволява да направите това. Да, но How TreeMap се справя с това?

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

Изпълнението на този code ни дава грешка:

Проблемът е, че вътрешно класът TreeMap сравнява стойности с помощта на метода compareTo() . Със сигурност можете да подадете нулева стойност и codeът ще се компorра. Но по време на изпълнение ще получите грешка, тъй като методът ще бъде извикан при нулева стойност, което ще доведе до хвърляне на NullPointerException .

Сравнение на HashMap и TreeMap

За разлика от TreeMap , HashMap ви позволява да съхранявате null като ключ. Структурата има определено място за всички нулеви ключове. HashMap може да съхранява нулеви ключове, защото определя къде отиват въз основа на тяхната хеш стойност, а изчисляването на хеш стойността не изисква сравнения. Така че всички нулеви ключове имат своето място.

Ето го – сега знаете Howво да използвате, когато трябва да съхранявате стойности в сортиран ред и How да зададете правилата за сортиране.