TreeMap w Javie

Jeśli czytasz ten artykuł, najprawdopodobniej znasz interfejs Mapy i miejsca, w których można go odpowiednio zastosować. Jeśli nie, to przyjdź tutaj . Dzisiaj porozmawiamy o cechach implementacji Java TreeMap, a dokładniej o tym, czym różni się ona od HashMap i jak prawidłowo z niej korzystać.

Porównanie TreeMap, HashMap i LinkedHashMap

Najczęściej używaną implementacją interfejsu Map jest HashMap. Jest łatwy w użyciu i gwarantuje szybki dostęp do danych, więc jest najlepszym kandydatem do rozwiązania większości problemów. Większość, ale nie wszystkie. Czasami trzeba przechowywać dane w uporządkowany sposób i móc się po nich poruszać. W tym przypadku z pomocą przychodzi inna implementacja interfejsu Map (TreeMap). TreeMap implementuje interfejs NavigableMap , który dziedziczy SortedMap , który z kolei dziedziczy interfejs Map. Implementując interfejsy NavigableMap i SortedMap , TreeMap otrzymuje dodatkową funkcjonalność, która nie jest dostępna w HashMap, ale płaci cenę w postaci wydajności. Istnieje również LinkedHashMapclass , która pozwala również przechowywać dane w określonej kolejności (kolejność, w jakiej dodajesz je do mapy). Aby zrozumieć różnice między tymi trzema klasami, spójrz na tę tabelę: Jak widać, te zajęcia mają ze sobą wiele wspólnego, ale jest też kilka różnic. Chociaż klasa TreeMap jest najbardziej wszechstronna, nie zawsze może przechowywać wartość null jako klucz. Ponadto dostęp do elementów TreeMap zajmuje najwięcej czasu. Tak więc, jeśli nie musisz przechowywać danych w jakiejś posortowanej kolejności, lepiej jest użyć HashMap lub LinkedHashMap .

Drzewo czerwono-czarne

Prawdopodobnie zauważyłeś, że pod maską TreeMap używa struktury danych zwanej czerwono-czarnym drzewem. Przechowywanie danych w tej strukturze jest właśnie tym, co zapewnia porządkowanie danych. Więc co to za drzewo? Rozwiążmy to! Wyobraź sobie, że musisz przechowywać pary ciągów liczb. Liczby 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 i 101 będą kluczami. Jeśli przechowujesz dane na tradycyjnej liście i musisz znaleźć element z kluczem 101, będziesz musiał przejść przez wszystkie 13 elementów, aby go znaleźć. Dla 13 elementów to nie jest wielka sprawa, ale pracując z milionem, będziemy mieli duże problemy. Aby rozwiązać te problemy, programiści używają nieco bardziej złożonych struktur danych. W tym momencie na scenę wkracza czerwono-czarne drzewo!Wyszukiwanie elementu zaczyna się od korzenia drzewa, którym w naszym przypadku jest 61. Następnie porównujemy wartości węzłów z wartością, której szukamy. Jeśli nasza wartość jest mniejsza, to idziemy w lewo; jeśli jest większy, to idziemy w prawo. Proces ten powtarza się, dopóki nie znajdziemy pożądanej wartości lub napotkamy element, którego wartość jest zerowa (liść drzewa). Kolory czerwony i czarny służą do uproszczenia nawigacji i równoważenia drzewa. Istnieją zasady, których należy zawsze przestrzegać podczas budowania czerwono-czarnego drzewa:

• Korzeń musi być czarny.
• Liście drzewa muszą być czarne.
• Czerwony węzeł musi mieć dwa czarne węzły potomne.
• Czarny węzeł może mieć węzły potomne dowolnego koloru.
• Ścieżka od węzła do jego liści musi zawierać taką samą liczbę czarnych węzłów.
• Nowe węzły są dodawane do liści.

Jeśli rozważysz Reguły 3, 4 i 5 razem, możesz zrozumieć, w jaki sposób kolor węzłów pozwala nam szybciej poruszać się po drzewie: ścieżka przez czarne węzły jest zawsze krótsza niż przez czerwone węzły. W związku z tym całkowity rozmiar drzewa zależy od liczby czarnych węzłów, co nazywa się „czarną wysokością”. Struktura danych drzewa czerwono-czarnego jest realizowana w różnych językach programowania. W Internecie jest wiele implementacji Javy, więc nie będziemy się tu zatrzymywać. Zamiast tego kontynuujmy poznawanie funkcjonalności TreeMap.

Metody pochodzące z interfejsów SortedMap i NavigableMap

Podobnie jak HashMap, TreeMap implementuje interfejs Map, co oznacza, że ​​TreeMap posiada wszystkie metody istniejące w HashMap. Ale TreeMap implementuje również interfejsy SortedMap i NavigableMap , dzięki czemu uzyskuje z nich dodatkową funkcjonalność. SortedMap to interfejs, który rozszerza Map i dodaje metody odpowiednie do posortowanego zbioru danych:

• firstKey() : zwraca klucz pierwszego elementu na mapie
• lastKey() : zwraca klucz ostatniego elementu
• headMap(K end) : zwraca mapę, która zawiera wszystkie elementy bieżącej mapy, od początku do elementu z kluczowym końcem
• tailMap(K start) : zwraca mapę zawierającą wszystkie elementy bieżącej mapy, od elementu początkowego do końca
• subMap(K start, K ​​end) : zwraca mapę zawierającą wszystkie elementy bieżącej mapy, od elementu początkowego do elementu z kluczowym końcem.

NavigableMap to interfejs, który rozszerza SortedMap i dodaje metody do nawigacji między elementami mapy:

• firstEntry() : zwraca pierwszą parę klucz-wartość
• lastEntry() : zwraca ostatnią parę klucz-wartość
• pollFirstEntry() : zwraca i usuwa pierwszą parę
• pollLastEntry() : zwraca i usuwa ostatnią parę
• ceilingKey(K obj) : zwraca najmniejszy klucz k, który jest większy lub równy kluczowi obj. Jeśli nie ma takiego klucza, zwraca wartość null
• floorKey(K obj) : zwraca największy klucz k, który jest mniejszy lub równy kluczowi obj. Jeśli nie ma takiego klucza, zwraca wartość null
• lowerKey(K obj) : zwraca największy klucz k, który jest mniejszy niż klucz obj. Jeśli nie ma takiego klucza, zwraca wartość null
• wyższyKey(K obj) : zwraca najmniejszy klucz k, który jest większy niż klucz obj. Jeśli nie ma takiego klucza, zwraca wartość null
• ceilingEntry(K obj) : podobnie jak metoda ceilingKey(K obj), zwraca tylko parę klucz-wartość (lub wartość null)
• floorEntry(K obj) : podobnie jak metoda floorKey(K obj), zwraca tylko parę klucz-wartość (lub wartość null)
• lowerEntry(K obj) : podobnie jak metoda lowerKey(K obj), zwraca tylko parę klucz-wartość (lub null)
• highEntry(K obj) : podobnie jak metoda highKey(K obj), zwraca tylko parę klucz-wartość (lub wartość null)
• maleingKeySet() : zwraca NavigableSet zawierający wszystkie klucze posortowane w odwrotnej kolejności
• maleingMap() : zwraca NavigableMap zawierającą wszystkie pary posortowane w odwrotnej kolejności
• navigableKeySet() : zwraca obiekt NavigableSet zawierający wszystkie klucze w kolejności, w jakiej są przechowywane
• headMap(K upperBound, boolean incl) : zwraca mapę zawierającą pary od początku do elementu upperBound. Parametr incl wskazuje, czy uwzględnić element upperBound w zwróconej mapie
• tailMap(K lowerBound, boolean incl) : funkcjonalność podobna do poprzedniej metody, zwraca tylko pary od lowerBound do końca
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : podobnie jak w przypadku poprzednich metod, zwraca pary od lowerBound do upperBound; argumenty lowIncl i highIncl wskazują, czy uwzględnić elementy brzegowe na nowej mapie.

Oprócz zwykłych konstruktorów TreeMap ma jeszcze jeden konstruktor, który akceptuje instancję komparatora. Komparator ten odpowiada za kolejność przechowywania elementów.

Przykłady TreeMap

Ta obfitość dodatkowych metod może wydawać się zbędna, ale okazują się one znacznie bardziej przydatne, niż mogłoby się wydawać na pierwszy rzut oka. Przeanalizujmy razem następujący przykład. Wyobraź sobie, że pracujemy w dziale marketingu dużej firmy i mamy bazę osób, którym chcemy wyświetlać reklamy. Należy pamiętać o dwóch szczegółach:

• Musimy śledzić liczbę wyświetleń dla każdej osoby
• Algorytm wyświetlania reklam nieletnim jest inny.

Stwórzmy klasę Person , która będzie przechowywać wszystkie istotne informacje o każdej osobie:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Implementujemy logikę w klasie Main :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

W klasie Main utwórz TreeMap, w której każdy klucz reprezentuje konkretną osobę, a każda wartość to liczba wyświetleń reklamy w tym miesiącu. Przekazujemy konstruktorowi komparator, który sortuje ludzi według wieku. Wypełniamy mapę dowolnymi wartościami. Teraz chcemy uzyskać odniesienie do pierwszego dorosłego w naszym małym repozytorium danych. Robimy to za pomocą Stream API. Otrzymujemy wtedy dwie osobne mapy, które przekazujemy do metod wyświetlających reklamy. Jest wiele, wiele sposobów, w jakie mogliśmy wykonać to zadanie. Arsenał metod klasy TreeMap pozwala nam tworzyć niestandardowe rozwiązania dla każdej potrzeby. Nie musisz ich wszystkich pamiętać, ponieważ zawsze możesz skorzystać z dokumentacji lub wskazówek ze swojego IDE. Aby utrwalić to, czego się nauczyłeś, zalecamy obejrzenie lekcji wideo z naszego kursu języka Java

To wszystko na teraz! Mam nadzieję, że klasa TreeMap jest teraz dla Ciebie jasna i że zastosujesz ją właściwie w rozwiązywaniu praktycznych zadań związanych z kodowaniem.