Особливості TreeMap в Java

Якщо ти читаєш цю статтю, найімовірніше, ти знайомий з інтерфейсом Map і варіантами його застосування. Якщо ні, то тобі сюди. Сьогодні ми поговоримо про особливості реалізації TreeMap, а саме – чим вона відрізняється від HashMap і як правильно її використовувати.

Порівняння TreeMap, HashMap і LinkedHashMap

Найбільш використовувана імплементація інтерфейсу Map – це HashMap. Вона проста у використанні та гарантує швидкий доступ до даних, тому це найкращий кандидат для вирішення більшості завдань. Більшості, але не всіх. Іноді необхідно зберігати дані в структурованому вигляді з можливістю навігації по них. У такому разі на допомогу приходить інша реалізація інтерфейсу Map – TreeMap. TreeMap імплементує інтерфейс NavigableMap, який успадковується від SortedMap, а він, зі свого боку, від інтерфейсу Map. Імплементуючи інтерфейси NavigableMap і SortedMap, TreeMap отримує додатковий функціонал, якого немає в HashMap, але плата за це – продуктивність. Існує ще клас LinkedHashMap, який теж дає змогу зберігати дані в певному порядку – у порядку додавання. Щоб тобі були зрозумілі відмінності між цими трьома класами, подивися на цю таблицю:Як бачиш, у цих класах є багато спільного, але і є кілька відмінностей. Хоч клас TreeMap є найбільш багатофункціональним, він не завжди може зберігати null як ключ. Крім цього, час доступу до елементів TreeMap буде найтривалішим. Тому якщо тобі не потрібно зберігати дані у відсортованому вигляді, краще використовуй HashMap або LinkedHashMap.

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

Як ти напевно помітив, під капотом TreeMap використовує структуру даних, яка називається червоно-чорне дерево. Саме зберігання даних у цій структурі й забезпечує порядок зберігання даних. Що ж являє собою це дерево? Давай розбиратися! Уяви, що тобі необхідно зберігати пари "Число-Рядок". Числа 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 будуть ключами. Якщо ти зберігаєш дані в традиційному списку і з'являється необхідність знайти елемент із ключем 101, потрібно буде перебрати всі 13 елементів під час його пошуку. Для 13 елементів це не критично, а ось під час роботи з мільйоном у нас виникнуть великі неприємності. Для вирішення таких проблем програмісти використовують трохи складніші структури даних. Тож зустрічай червоно-чорне дерево!

Джерело

Пошук потрібного елемента починається з кореня дерева, у нашому випадку це 61. Далі відбувається порівняння з необхідним значенням. Якщо наше значення менше – вирушаємо в лівий бік, якщо більше – у правий. Так відбувається, допоки не знайдемо необхідне значення або не впремося в елемент зі значенням null (листок дерева). Червоні та чорні кольори використовуються для спрощення навігації по дереву і його балансування. Існують правила, яких завжди слід дотримуватися під час побудови червоно-чорного дерева:

• Корінь має бути забарвлений у чорний колір.
• Листя дерева має бути чорного кольору.
• Червоний вузол повинен мати два чорних дочірніх вузла.
• Чорний вузол може мати будь-які дочірні вузли.
• Шлях від вузла до його листя має містити однакову кількість чорних вузлів.
• Нові вузли додаються на місця листя.

Якщо подивитися на правила 3, 4 і 5 сукупно, можна зрозуміти, як забарвлення вузлів прискорює навігацію по дереву: шлях через чорні вузли завжди коротший, ніж через червоні. Тому за кількістю саме чорних вузлів і визначається загальний розмір дерева, і називається цей розмір "чорна висота". Червоно-чорне дерево реалізують різними мовами програмування. В інтернеті існує купа реалізацій для Java, тому не будемо на ньому зупинятися надовго, а продовжимо знайомство з функціоналом TreeMap.

Методи, отримані з інтерфейсів 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.

NavigableMap – інтерфейс, який розширює SortedMap і додає методи для навігації між елементами мапи:

• 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, крім звичних нам конструкторів, додається ще один, який приймає екземпляр компаратора. Цей компаратор і відповідатиме за порядок зберігання елементів.

Приклади використання TreeMap

Такий достаток додаткових методів може здатися непотрібним, але дуже часто вони виявляються куди кориснішими, ніж здавалося спочатку. Давай розглянемо з тобою ось такий приклад. Уяви, що ми працюємо в маркетинговому відділі великої компанії, і в нас є база людей, яким ми хочемо показувати рекламу. Водночас є два нюанси:

• нам потрібно вести облік кількості показів кожній людині;
• алгоритм показу реклами для неповнолітніх відрізняється.

Створимо клас 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;
   }
}

Логіку реалізуємо в класі 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 для тебе зрозумілий, і ти знайдеш йому точне застосування в розв'язанні практичних завдань.