Funkcje TreeMap w Javie

Jeśli czytasz ten artykuł, prawdopodobnie znasz interfejs Mapy i jego zastosowania. Jeśli nie, to proszę bardzo. Dzisiaj porozmawiamy o funkcjach implementacyjnych TreeMap, a dokładniej o tym, czym różni się ona od HashMap i jak poprawnie z niej korzystać.

Porównanie TreeMap, HashMap i LinkedHashMap

Najczęściej stosowaną implementacją interfejsu Map jest HashMap . Jest łatwy w obsłudze i gwarantuje szybki dostęp do danych, co czyni go najlepszym kandydatem do większości zadań. Większość, ale nie wszystkie. Czasami konieczne jest przechowywanie danych w ustrukturyzowanej formie z możliwością poruszania się po nich. W tym przypadku na ratunek przychodzi kolejna implementacja interfejsu Map – TreeMap . TreeMap implementuje interfejs NavigableMap , który dziedziczy z SortedMap , który z kolei dziedziczy z interfejsu Map . Implementując interfejsy NavigableMap i SortedMap , TreeMap zyskuje dodatkową funkcjonalność, której HashMap nie ma , ale ma to swoją cenę pod względem wydajności. Istnieje również klasa LinkedHashMap , która również pozwala na przechowywanie danych w określonej kolejności – w kolejności, w jakiej zostały dodane. Aby pomóc Ci zrozumieć różnice między tymi trzema klasami, spójrz na poniższą tabelę: Jak widać, klasy te mają wiele wspólnego, ale jest też kilka różnic. Chociaż klasa TreeMapjest najbardziej wielofunkcyjna, nie zawsze można ją przechowywać nulljako klucz. Dodatkowo czas dostępu do elementów TreeMap będzie najdłuższy. Dlatego jeśli nie musisz przechowywać danych w formie posortowanej, lepiej użyć HashMaplub LinkedHashMap.

Drzewo czerwono-hebanowe

Jak zapewne zauważyłeś, pod maską TreeMapwykorzystuje strukturę danych zwaną czerwono-czarnym drzewem. To właśnie przechowywanie danych w tej strukturze zapewnia porządek, w jakim dane są przechowywane. Co to za drzewo? Rozwiążmy to! Wyobraź sobie, że musisz przechowywać pary Liczba-Ciąg. Kluczami będą liczby 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101. Jeśli przechowujesz dane na tradycyjnej liście i chcesz znaleźć element z kluczem 101, będziesz musiał przejść przez wszystkie 13 elementów, aby go znaleźć. Dla 13 elementów nie jest to krytyczne, przy pracy z milionem będziemy mieli duże kłopoty. Aby rozwiązać takie problemy, programiści używają nieco bardziej złożonych struktur danych. Poznaj więc czerwono-czarne drzewo!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Poszukiwanie potrzebnego elementu rozpoczynamy od korzenia drzewa, w naszym przypadku jest to 61. Następnie następuje porównanie z wymaganą wartością. Jeśli nasza wartość jest mniejsza, idziemy w lewo, jeśli jest większa, idziemy w prawo. Dzieje się tak dopóki nie znajdziemy wymaganej wartości lub nie trafimy na element z wartością null(liść drzewa). Aby ułatwić nawigację i równowagę po drzewie, zastosowano kolory czerwony i czarny. Budując czerwono-czarne drzewo, należy zawsze przestrzegać zasad:

• Korzeń powinien mieć kolor czarny.
• Liście drzewa powinny być czarne.
• Czerwony węzeł musi mieć dwa czarne węzły podrzędne.
• Czarny węzeł może mieć dowolne węzły podrzędne.
• Ścieżka od węzła do jego liści musi zawierać taką samą liczbę czarnych węzłów.
• W miejsce liści dodawane są nowe węzły.

Jeśli spojrzysz na zasady 3, 4 i 5 razem, możesz zrozumieć, jak kolorowanie węzłów przyspiesza nawigację po drzewie: ścieżka przez czarne węzły jest zawsze krótsza niż przez czerwone. Dlatego całkowity rozmiar drzewa zależy od liczby czarnych węzłów, a rozmiar ten nazywany jest „czarną wysokością”. Drzewo czerwono-czarne jest implementowane w różnych językach programowania. W Internecie istnieje wiele implementacji Java, więc nie będziemy się nad tym długo rozwodzić, ale nadal będziemy zapoznawać się z funkcjonalnością TreeMap.

Metody wywodzące się z interfejsów SortedMap i NavigableMap

Podobnie HashMap, TreeMapimplementuje interfejs Map, co oznacza, że TreeMap​​posiada wszystkie metody, które HashMap. Ale dodatkowo TreeMapimplementuje interfejsy SortedMapi NavigableMapuzyskuje z nich dodatkową funkcjonalność. SortedMap— interfejs rozszerzający Mapi dodający metody istotne dla posortowanego zbioru danych:

• firstKey(): zwraca klucz pierwszego elementu mapy;
• lastKey(): zwraca klucz ostatniego elementu;
• headMap(K end): zwraca mapę zawierającą wszystkie elementy aktualnej od początku do elementu z kluczem end;
• tailMap(K start): zwraca mapę zawierającą wszystkie elementy bieżącej mapy, zaczynając od elementu starti kończąc na końcu;
• subMap(K start, K end): zwraca mapę zawierającą wszystkie elementy bieżącej mapy, zaczynając od elementu starti kończąc na elemencie z kluczem end.

NavigableMap— interfejs rozszerzający SortedMapi dodający metody nawigacji pomię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 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 null;
• lowerKey(K obj): Zwraca największy klucz k, który jest mniejszy niż klucz obj. Jeśli nie ma takiego klucza, zwraca null;
• higherKey(K obj): Zwraca najmniejszy klucz k większy niż klucz obj. Jeśli nie ma takiego klucza, zwraca null;
• ceilingEntry(K obj): podobny do metody sufitKey(K obj), ale zwraca parę klucz-wartość (lub wartość null);
• floorEntry(K obj): podobny do metody FloorKey(K obj), ale zwraca parę klucz-wartość (lub wartość null);
• lowerEntry(K obj): podobny do metody lessKey(K obj), ale zwraca parę klucz-wartość (lub wartość null);
• higherEntry(K obj): podobny do metody validKey(K obj), ale zwraca parę klucz-wartość (lub wartość null);
• descendingKeySet(): zwraca NavigableSet zawierający wszystkie klucze posortowane w odwrotnej kolejności;
• descendingMap(): zwraca NavigableMap zawierającą wszystkie pary posortowane w odwrotnej kolejności;
• navigableKeySet(): zwraca obiekt NavigableSet zawierający wszystkie klucze w kolejności przechowywania;
• headMap(K upperBound, boolean incl): zwraca mapę zawierającą pary od początku do elementu UpperBound. Argument incl określa, czy element UpperBound powinien zostać uwzględniony w zwracanej mapie;
• tailMap(K lowerBound, boolean incl): funkcjonalność jest podobna do poprzedniej metody, zwracane są tylko pary od lessBound do końca;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Podobnie jak w poprzednich metodach zwracane są pary od LowerBound do UpperBound, argumenty lowIncl i highIncl określają, czy elementy graniczne mają zostać uwzględnione w nowej mapie.

W samej implementacji TreeMapoprócz znanych nam konstruktorów dodany zostaje jeszcze jeden, który akceptuje instancję komparatora. Komparator ten będzie odpowiedzialny za kolejność przechowywania elementów.

Przykłady wykorzystania TreeMap

Taka mnogość dodatkowych metod może wydawać się niepotrzebna, ale bardzo często okazują się one znacznie bardziej przydatne, niż początkowo się wydawało. Spójrzmy na ten przykład razem z tobą. Wyobraź sobie, że pracujemy w dziale marketingu dużej firmy i mamy bazę danych osób, którym chcemy wyświetlać reklamy. Są dwa niuanse:

• musimy śledzić liczbę wyświetleń każdej osobie;
• Algorytm wyświetlania reklam nieletnim jest inny.

Stwórzmy klasę Person, która będzie przechowywać wszystkie dostępne nam informacje o 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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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, Mainktórą tworzymy TreeMap, gdzie keyjest konkretna osoba i valuejest liczba wyświetleń reklamy w tym miesiącu. W konstruktorze przekazujemy komparator, który będzie sortował osoby według wieku. Wypełnij maplosowymi wartościami. Teraz musimy uzyskać odniesienie do pierwszej osoby dorosłej w naszym mini magazynie danych. Robimy to za pomocą Stream API. Następnie otrzymujemy dwie niezależne mapy, które przekazujemy metodom wyświetlającym reklamy. Istnieje wiele, wiele sposobów rozwiązania tego problemu. Arsenał metod zajęć TreeMappozwala wymyślić rozwiązania na każdy gust. Nie ma potrzeby zapamiętywania ich wszystkich, gdyż zawsze można skorzystać z dokumentacji lub podpowiedzi ze środowiska deweloperskiego. To wszystko! Mam nadzieję, że zajęcia są teraz TreeMapdla Ciebie jasne i znajdziesz dla nich precyzyjne zastosowanie w rozwiązywaniu problemów praktycznych.