TreeMap в Java

Ако четете тази статия, най-вероятно сте запознати с интерфейса на Map и къде може да се приложи по подходящ начин. Ако не, тогава ела тук . Днес ще говорим за характеристиките на внедряването на Java TreeMap и по-конкретно How се различава от HashMap и How да го използваме правилно.

Сравняване на TreeMap, HashMap и LinkedHashMap

Най-използваната реализация на интерфейса Map е HashMap. Той е лесен за използване и гарантира бърз достъп до данни, така че е най-добрият кандидат за решаване на повечето проблеми. Повечето, но не всички. Понякога трябва да съхранявате данни по структуриран начин и да можете да навигирате в тях. В този случай на помощ идва друга реализация на Map интерфейса (TreeMap). TreeMap имплементира интерфейса NavigableMap , който наследява SortedMap , който от своя страна наследява интерфейса Map. Чрез прилагането на интерфейсите NavigableMap и SortedMap , TreeMap получава допълнителна функционалност, която не е налична в HashMap, но плаща цена по отношение на производителността. Има и LinkedHashMapклас , който също ви позволява да съхранявате данни в определен ред (реда, в който ги добавяте към картата). За да разберете разликите между тези три класа, погледнете тази table: Както можете да видите, тези класове имат много общи неща, но има и няколко разлики. Въпреки че класът TreeMap е най-гъвкавият, той не винаги може да съхранява null като ключ. В допълнение, достъпът до елементите на TreeMap отнема най-дълго време. Така че, ако не е необходимо да съхранявате данни в няHowъв сортиран ред, по-добре е да използвате HashMap or LinkedHashMap .

Червено-черно дърво

Вероятно сте забелязали, че под капака TreeMap използва структура от данни, наречена червено-черно дърво. Съхраняването на данни в тази структура е точно това, което осигурява подреждането на данните. И така, Howъв вид дърво е това? Нека да го разберем! Представете си, че трябва да съхранявате двойки число-низ. Числата 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 и 101 ще бъдат ключове. Ако съхранявате данни в традиционен списък и трябва да намерите елемента с ключ 101, тогава ще трябва да преминете през всичките 13 елемента, за да го намерите. За 13 елемента това не е голяма работа, но когато работим с мorон, ще имаме големи проблеми. За да решат тези проблеми, програмистите използват малко по-сложни структури от данни. Тук на сцената излиза червено-черното дърво!Търсенето на елемент започва от корена на дървото, което в нашия случай е 61. След това сравняваме стойностите на възела със стойността, която търсим. Ако стойността ни е по-малка, тогава отиваме наляво; ако е по-голямо, отиваме надясно. Този процес се повтаря, докато намерим желаната стойност or срещнем елемент, чиято стойност е нула (лист от дървото). Цветовете червено и черно се използват за опростяване на навигацията и балансиране на дървото. Има правила, които винаги трябва да се спазват при изграждането на червено-черно дърво:

• Коренът трябва да е черен.
• Листата на дървото трябва да са черни.
• Червен възел трябва да има два черни дъщерни възела.
• Черният възел може да има дъщерни възли от произволен цвят.
• Пътят от възел до неговите листа трябва да съдържа същия брой черни възли.
• Към листата се добавят нови възли.

Ако разгледате правила 3, 4 и 5 заедно, можете да разберете How цветът на възлите ни позволява да навигираме по-бързо в дървото: пътят през черни възли винаги е по-къс от този през червени възли. Съответно, общият размер на дървото се определя от броя на черните възли, което се нарича "черна височина". Червено-черната дървовидна структура от данни е внедрена в различни езици за програмиране. В Интернет има много реализации на Java, така че няма да се задържаме тук. Вместо това, нека продължим да опознаваме функционалността на TreeMap.

Методи, които идват от интерфейсите SortedMap и NavigableMap

Подобно на HashMap, TreeMap имплементира интерфейса Map, което означава, че TreeMap има всички методи, които съществуват в HashMap. Но TreeMap също така имплементира интерфейсите SortedMap и NavigableMap и по този начин получава допълнителна функционалност от тях. SortedMap е интерфейс, който разширява Map и добавя методи, подходящи за сортиран набор от данни:

• firstKey() : връща ключа на първия елемент в картата
• lastKey() : връща ключа на последния елемент
• headMap(K край) : връща карта, която съдържа всички елементи на текущата карта, от началото до елемента с ключ край
• tailMap(K начало) : връща карта, която съдържа всички елементи на текущата карта, от началния елемент до края
• subMap(K начало, K край) : връща карта, която съдържа всички елементи на текущата карта, от началния елемент до елемента с ключ край.

NavigableMap е интерфейс, който разширява SortedMap и добавя методи за навигация между елементи на карта:

• firstEntry() : връща първата двойка ключ-стойност
• lastEntry() : връща последната двойка ключ-стойност
• pollFirstEntry() : връща и изтрива първата двойка
• pollLastEntry() : връща и изтрива последната двойка
• stropKey(K obj) : връща най-малкия ключ k, който е по-голям or equals на ключа obj. Ако няма такъв ключ, връща нула
• floorKey(K obj) : връща най-големия ключ k, който е по-малък or equals на ключа obj. Ако няма такъв ключ, връща нула
• lowerKey(K obj) : връща най-големия ключ k, който е по-малък от ключа obj. Ако няма такъв ключ, връща нула
• aboveKey(K obj) : връща най-малкия ключ k, който е по-голям от ключа obj. Ако няма такъв ключ, връща нула
• stropEntry(K obj) : подобно на метода stropKey(K obj), връща само двойка ключ-стойност (or нула)
• floorEntry(K obj) : подобно на метода floorKey(K obj), връща само двойка ключ-стойност (or нула)
• lowerEntry(K obj) : подобно на метода lowerKey(K obj), връща само двойка ключ-стойност (or нула)
• aboveEntry(K obj) : подобно на метода aboveKey(K obj), връща само двойка ключ-стойност (or нула)
• descendingKeySet() : връща NavigableSet, съдържащ всички ключове, сортирани в обратен ред
• descendingMap() : връща NavigableMap, съдържаща всички двойки, сортирани в обратен ред
• navigableKeySet() : връща обект NavigableSet, съдържащ всички ключове в реда, в който са съхранени
• headMap(K upperBound, boolean incl) : връща карта, която съдържа двойки от началото до елемента upperBound. Параметърът incl показва дали да се включи елементът upperBound в върнатата карта
• tailMap(K lowerBound, boolean incl) : функционалност, подобна на предишния метод, връща само двойки от lowerBound до края
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : Howто при предишните методи, връща двойки от lowerBound до upperBound; аргументите lowIncl и highIncl показват дали да се включат граничните елементи в новата карта.

В допълнение към обичайните конструктори, TreeMap има друг конструктор, който приема екземпляр на компаратор. Този компаратор е отговорен за реда, в който се съхраняват елементите.

Примери за TreeMap

Това изобorе от допълнителни методи може да изглежда ненужно, но те се оказват много по-полезни, отколкото може да си представите на пръв поглед. Нека заедно разгледаме следния пример. Представете си, че работим в маркетинговия отдел на голяма компания и имаме база данни с хора, на които искаме да показваме реклами. Има две подробности, които трябва да имате предвид:

• Трябва да следим броя импресии за всеки човек
• Алгоритъмът за показване на реклами на непълнолетни е различен.

Нека създадем клас Person , който ще съхранява цялата необходима информация за всеки човек:

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;
   }
}

Ние прилагаме логиката в основния клас:

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) {}
}

В главния клас създайте TreeMap, в която всеки ключ представлява конкретно лице и всяка стойност е броят рекламни импресии този месец. Предаваме на конструктора компаратор, който сортира хората по възраст. Запълваме картата с произволни стойности. Сега искаме да получим препратка към първия възрастен в нашето малко хранorще на данни. Ние правим това с помощта на Stream API. След това получаваме две отделни карти, които предаваме на методите, които показват реклами. Има много, много начини, по които бихме могли да изпълним тази задача. Арсеналът от методи на класа TreeMap ни позволява да създаваме персонализирани решения за всяка нужда. Не е необходимо да ги помните всички, защото винаги можете да използвате documentацията or съветите от вашата IDE. За да затвърдите наученото, ви предлагаме да гледате видео урок от нашия курс по Java Това е всичко за сега! Надявам се, че класът TreeMap вече ви е ясен и че ще го приложите правилно при решаването на практически задачи за codeиране.