Знакомство с коллекцией 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 ключей есть свое место.

Итак, теперь ты знаешь, что использовать, когда тебе нужно хранить значения в отсортированном порядке, и как задавать правила и порядок сортировки.