Особенности 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 элементов это не критично, при работе с миллионом у нас возникнут большие неприятности. Для решения таких проблем программисты используют немного более сложные структуры данных. Поэтому встречай красно-чёрное дерево!

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

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