Ознайомлення з колекцією TreeMap

Одного разу в університеті мені потрібно було написати завдання для сортування в порядку зростання прізвищ, які були ключами до особистих справ моїх одногрупників, і я витратив на це чимало часу. Але якби тоді я мав уявлення про клас TreeMap, це в мене вийшло б набагато швидше.

Що таке TreeMap? Це структура даних, схожа на словник, яка дає можливість зберігати елементи у вигляді ключ-значення, використовуючи сортування за ключами.

Де і як його можна використати? Наприклад, у тому самому випадку з одногрупниками. Якщо мені потрібно зберігати значення в порядку зростання замість того, щоб писати свої алгоритми сортування, достатньо створити TreeMap і покласти значення туди.

Для таких типів як Integer і String використовується порядок сортування за зростанням. Але якщо ти хочеш покласти в TreeMap власний тип, потрібно щоб твій клас імплементував інтерфейс Comparable, у класі був реалізований метод compareTo() і вказано, як потрібно сортувати значення цього класу.

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 використовувати для зберігання дерева і зберігати значення у відсортованому порядку.

Якщо говорити простими словами, червоно-чорне дерево — це структура даних, що зберігає праворуч значення, які більші за кореневе, а ліворуч — ті, що менше. Така реалізація допомагає швидше шукати значення у структурі.

Червоно-чорне дерево є самобалансуючим, тому за кожної нової вставки воно змінюватиме свою структуру, оскільки додаються нові значення. Кореневим вважається значення, додане першим, але у процесі балансування кореневим може стати і друге значення.

Отже, тепер ти знаєш, що таке TreeMap і за яким принципом воно працює.

Важливо пам’ятати, що зберігати в TreeMap можна тільки тих, хто імплементував Comparable інтерфейс і перевизначив метод compareTo().

Але що робити, якщо ми використовуємо сторонні класи, які підвантажуємо з інших бібліотек, і не можемо імплементувати в них 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, потрібно вказати, як їх сортувати. Зробити це можна двома способами: імплементувати Comparable або реалізувати свій Comparator.

Але що, якщо нам потрібно покласти в TreeMap значення null як ключ? HashMap дозволяє це зробити. А як же працює із цим TreeMap?

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

Запустивши цей код, отримаємо помилку:

Проблема полягає у тому, що всередині класу TreeMap відбувається порівняння значень методом compareTo(). Ти, звичайно ж, можеш покласти туди null значення, і воно скомпілюється, але в рантаймі ти отримаєш помилку, оскільки на значенні null викличеться метод і вилетить NullPointerException.

Порівняння HashMap і TreeMap

На відміну від TreeMap, у HashMap дозволено зберігати null як ключ. Для всіх null ключів виділено певне місце у структурі. Зберігати null ключі в HashMap дозволяє те, що визначення місця тут відбувається за значенням хеша, і для цього не потрібно порівнювати значення з іншими. Тому всі null ключі мають своє місце.

Отже, тепер ти знаєш, що використовувати, коли потрібно зберігати значення у відсортованому порядку, і як задавати правила і порядок сортування.