Wprowadzenie do kolekcji TreeMap

Kiedyś na uniwersytecie musiałem napisać zadanie sortowania rosnąco nazwisk, które były kluczami do osobistych teczek moich kolegów z klasy, i spędziłem nad tym dużo czasu. Ale gdybym wtedy znał klasę TreeMap , zrobiłbym to znacznie szybciej.

Co to jest TreeMap ? Jest to podobna do słownika struktura danych, która umożliwia przechowywanie elementów jako klucz-wartość przy użyciu sortowania według klucza.

Gdzie i jak można go wykorzystać? Na przykład w tej samej sprawie z kolegami z klasy. Jeśli potrzebuję przechowywać wartości w porządku rosnącym, zamiast pisać własne algorytmy sortowania, wystarczy stworzyć TreeMap i umieścić tam wartości.

W przypadku typów, takich jak Integer i String, używana jest rosnąca kolejność sortowania. Ale jeśli chcesz umieścić swój własny typ w TreeMap , potrzebujesz swojej klasy do implementacji interfejsu Comparable , metody CompareTo() do zaimplementowania w klasie i należy określić, w jaki sposób mają być sortowane wartości tej klasy .

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

Zaimplementujmy ponownie metodę CompareTo() w celu posortowania wartości w malejącej kolejności alfabetycznej nazwy:

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

Wartości będą przechowywane w następującej kolejności:

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

Klasa TreeMap implementuje interfejs NavigableMap , który z kolei rozszerza SortedMap . Dzięki temu klasa TreeMap może przechowywać drzewa i przechowywać wartości w posortowanej kolejności.

Mówiąc najprościej, czerwono-czarne drzewo to struktura danych, która przechowuje wartości po prawej stronie, które są większe niż korzeń, a po lewej te, które są mniejsze. Implementacja ta pomaga szybko wyszukać wartości w strukturze.

Czerwono-czarne drzewo samo się równoważy, więc przy każdym nowym wstawieniu będzie zmieniać swoją strukturę w miarę dodawania nowych wartości. Pierwiastek jest wartością dodaną jako pierwszą, ale podczas procesu równoważenia pierwiastkiem może stać się inna wartość.

Więc teraz wiesz, czym jest TreeMap i jak działa.

Należy pamiętać, że tylko te, które zaimplementowały interfejs Comparable i zastąpiły metodę CompareTo() , mogą być przechowywane w TreeMap .

Ale co, jeśli użyjemy klas innych firm, które są ładowane z innych bibliotek i nie możemy w nich zaimplementować Comparable ? Na takie przypadki istnieje rozwiązanie: napisz własny Comparator .

Comparator to interfejs, który ma metodę Compare(). Dzięki niemu możemy porównywać obiekty i przechowywać je w 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);

W tym przykładzie utworzyliśmy niestandardowy Comparator i przekazaliśmy TreeMap do klasy.

Od wersji Java 8 można to zapisać za pomocą wyrażenia lambda:

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

Oznacza to, że aby przechowywać wartości w TreeMap , musisz określić sposób ich sortowania. Można to zrobić na dwa sposoby: zaimplementuj Comparable lub zaimplementuj swój własny Comparator .

Ale co, jeśli musimy umieścić wartość null w TreeMap jako klucz? HashMap pozwala to zrobić. Ale jak to działa z tą mapą TreeMap ?

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

Uruchamiając ten kod, otrzymujemy błąd:

Problem polega na tym, że wewnątrz klasy TreeMap wartości są porównywane za pomocą metody CompareTo() . Oczywiście możesz umieścić tam wartość null i skompiluje się, ale w czasie wykonywania pojawi się błąd, ponieważ metoda zostanie wywołana na wartości null i zostanie zgłoszony wyjątek NullPointerException .

Porównanie HashMap i TreeMap

W przeciwieństwie do TreeMap , HashMap może przechowywać wartość null jako klucz. Wszystkie klucze zerowe mają przydzielone określone miejsce w strukturze. Przechowywanie kluczy zerowych w HashMap jest możliwe, ponieważ lokalizacja tutaj jest określana przez wartość skrótu, a do tego nie trzeba porównywać wartości z innymi. Dlatego wszystkie klucze zerowe mają swoje miejsce.

Więc teraz wiesz, czego użyć, gdy musisz przechowywać wartości w posortowanej kolejności oraz jak ustawić reguły i kolejność sortowania.