Якщо ти читаєш цю статтю, найімовірніше, ти знайомий з інтерфейсом Map і варіантами його застосування. Якщо ні, то тобі сюди. Сьогодні ми поговоримо про особливості реалізації TreeMap, а саме – чим вона відрізняється від HashMap і як правильно її використовувати.
Як бачиш, у цих класах є багато спільного, але і є кілька відмінностей. Хоч клас TreeMap є найбільш багатофункціональним, він не завжди може зберігати null як ключ. Крім цього, час доступу до елементів TreeMap буде найтривалішим.
Тому якщо тобі не потрібно зберігати дані у відсортованому вигляді, краще використовуй HashMap або LinkedHashMap.
Пошук потрібного елемента починається з кореня дерева, у нашому випадку це 61. Далі відбувається порівняння з необхідним значенням. Якщо наше значення менше – вирушаємо в лівий бік, якщо більше – у правий. Так відбувається, допоки не знайдемо необхідне значення або не впремося в елемент зі значенням null (листок дерева). Червоні та чорні кольори використовуються для спрощення навігації по дереву і його балансування. Існують правила, яких завжди слід дотримуватися під час побудови червоно-чорного дерева:
Порівняння TreeMap, HashMap і LinkedHashMap
Найбільш використовувана імплементація інтерфейсу Map – це HashMap. Вона проста у використанні та гарантує швидкий доступ до даних, тому це найкращий кандидат для вирішення більшості завдань. Більшості, але не всіх. Іноді необхідно зберігати дані в структурованому вигляді з можливістю навігації по них. У такому разі на допомогу приходить інша реалізація інтерфейсу Map – TreeMap. TreeMap імплементує інтерфейс NavigableMap, який успадковується від SortedMap, а він, зі свого боку, від інтерфейсу Map. Імплементуючи інтерфейси NavigableMap і SortedMap, TreeMap отримує додатковий функціонал, якого немає в HashMap, але плата за це – продуктивність. Існує ще клас LinkedHashMap, який теж дає змогу зберігати дані в певному порядку – у порядку додавання. Щоб тобі були зрозумілі відмінності між цими трьома класами, подивися на цю таблицю:HashMap | LinkedHashMap | TreeMap | |
---|---|---|---|
Порядок зберігання даних | Випадковий. Немає гарантій, що порядок збережеться протягом часу | У порядку додавання | У порядку зростання або виходячи із заданого компаратора |
Час доступу до елементів | O(1) | O(1) | O(log(n)) |
Імплементовані інтерфейси | Map | Map | NavigableMap SortedMap Map |
Імплементація на основі структури даних | Кошики (buckets) | Кошики (buckets) | Червоно-чорне дерево (Red-Black Tree) |
Можливість роботи з null-ключем | Можна | Можна | Можна, якщо використовується компаратор, що дозволяє null |
Потокобезпечна | Ні | Ні | Ні |
Червоно-чорне дерево
Як ти напевно помітив, під капотом TreeMap використовує структуру даних, яка називається червоно-чорне дерево. Саме зберігання даних у цій структурі й забезпечує порядок зберігання даних. Що ж являє собою це дерево? Давай розбиратися! Уяви, що тобі необхідно зберігати пари "Число-Рядок". Числа 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 будуть ключами. Якщо ти зберігаєш дані в традиційному списку і з'являється необхідність знайти елемент із ключем 101, потрібно буде перебрати всі 13 елементів під час його пошуку. Для 13 елементів це не критично, а ось під час роботи з мільйоном у нас виникнуть великі неприємності. Для вирішення таких проблем програмісти використовують трохи складніші структури даних. Тож зустрічай червоно-чорне дерево!- Корінь має бути забарвлений у чорний колір.
- Листя дерева має бути чорного кольору.
- Червоний вузол повинен мати два чорних дочірніх вузла.
- Чорний вузол може мати будь-які дочірні вузли.
- Шлях від вузла до його листя має містити однакову кількість чорних вузлів.
- Нові вузли додаються на місця листя.
Методи, отримані з інтерфейсів SortedMap і NavigableMap
Як і HashMap, TreeMap імплементує інтерфейс Map, а це означає, що в TreeMap є всі ті методи, що і в HashMap. Але до того ж TreeMap реалізує інтерфейси SortedMap і NavigableMap, отримуючи додатковий функціонал із них. SortedMap – інтерфейс, який розширює Map і додає методи, актуальні для відсортованого набору даних:- firstKey(): повертає ключ першого елемента мапи;
- lastKey(): повертає ключ останнього елемента;
- headMap(K end): повертає мапу, яка містить усі елементи поточної, від початку до елемента з ключем end;
- tailMap(K start): повертає мапу, яка містить усі елементи поточної, починаючи з елемента start і до кінця;
- subMap(K start, K end): повертає мапу, яка містить усі елементи поточної, починаючи з елемента start і до елемента з ключем end.
- firstEntry(): повертає першу пару "ключ-значення";
- lastEntry(): повертає останню пару "ключ-значення";
- pollFirstEntry(): повертає і видаляє першу пару;
- pollLastEntry(): повертає і видаляє останню пару;
- ceilingKey(K obj): повертає найменший ключ k, який більший або дорівнює ключу obj. Якщо такого ключа немає, повертає null;
- floorKey(K obj): повертає найбільший ключ k, який менший або дорівнює ключу obj. Якщо такого ключа немає, повертає null;
- lowerKey(K obj): повертає найбільший ключ k, який менший за ключ obj. Якщо такого ключа немає, повертає null;
- higherKey(K obj): повертає найменший ключ k, який більший за ключ obj. Якщо такого ключа немає, повертає null;
- ceilingEntry(K obj): аналогічний методу ceilingKey(K obj), тільки повертає пару "ключ-значення" (або null);
- floorEntry(K obj): аналогічний методу floorKey(K obj), тільки повертає пару "ключ-значення" (або null);
- lowerEntry(K obj): аналогічний методу lowerKey(K obj), тільки повертає пару "ключ-значення" (або null);
- higherEntry(K obj): аналогічний методу higherKey(K obj), тільки повертає пару "ключ-значення" (або null);
- 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): як і в попередніх методах, повертаються пари від lowerBound і до upperBound, аргументи lowIncl і highIncl вказують, чи додавати граничні елементи до нової мапи.
Приклади використання TreeMap
Такий достаток додаткових методів може здатися непотрібним, але дуже часто вони виявляються куди кориснішими, ніж здавалося спочатку. Давай розглянемо з тобою ось такий приклад. Уяви, що ми працюємо в маркетинговому відділі великої компанії, і в нас є база людей, яким ми хочемо показувати рекламу. Водночас є два нюанси:- нам потрібно вести облік кількості показів кожній людині;
- алгоритм показу реклами для неповнолітніх відрізняється.
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;
}
}
Логіку реалізуємо в класі 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){}
}
У класі Main створюємо TreeMap, де key – це конкретна людина, а value – кількість показів реклами в цьому місяці. У конструкторі передаємо компаратор, який відсортує людей за віком.
Заповнюємо map рандомними значеннями.
Тепер нам потрібно отримати посилання на першу дорослу людину в нашому міні-сховищі даних. Робимо це за допомогою Stream API.
Після цього отримуємо дві незалежні мапи, які передаємо в методи, що показують рекламу.
Існує дуже багато способів, якими можна було б вирішити це завдання. Арсенал методів класу TreeMap дає змогу винаходити рішення на будь-який смак. Запам'ятовувати їх усі не обов'язково, адже завжди можна скористатися документацією або підказками середовища розробки. На цьому все! Сподіваюся, тепер клас TreeMap для тебе зрозумілий, і ти знайдеш йому точне застосування в розв'язанні практичних завдань.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ