Особенности TreeMap в Java

TreeMap это реализация интерфейса Map, которая хранит пары “ключ-значение” отсортированными по ключу: либо по естественному порядку ключей, либо по правилу компаратора, переданного в конструктор. Внутри лежит красно-черное дерево, поэтому get, put и remove выполняются за O(log n), а не за O(1), как у HashMap. Взамен появляется навигация по данным: первый и последний элемент, ближайший больший или меньший ключ, срез по диапазону ключей. Если ты читаешь эту статью, скорее всего, ты знаком с интерфейсом Map и вариантами его применения. Если нет, то тебе сюда. Сегодня мы поговорим об особенностях реализации TreeMap, а конкретнее: чем она отличается от HashMap и как правильно ее использовать.

Кратко

• TreeMap держит пары в порядке сортировки ключей, HashMap порядок не гарантирует, LinkedHashMap хранит в порядке добавления.
• Порядок задается либо естественным сравнением ключей, либо компаратором, который передается в конструктор.
• Под капотом красно-черное дерево, отсюда O(log n) у основных операций против O(1) у HashMap.
• Из интерфейсов SortedMap и NavigableMap приходят методы навигации: firstKey(), lastKey(), ceilingKey(), floorKey(), headMap(), tailMap(), subMap().
• null в качестве ключа пройдет только с компаратором, который это разрешает: при естественном порядке будет NullPointerException.
• TreeMap не потокобезопасен и медленнее HashMap, поэтому бери его тогда, когда действительно нужен порядок или навигация по нему.

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

Наиболее используемая имплементация интерфейса Map это HashMap. Она простая в использовании и гарантирует быстрый доступ к данным, поэтому это лучший кандидат для решения большинства задач. Большинства, но не всех. Иногда необходимо хранить данные в структурированном виде с возможностью навигации по ним. В таком случае на помощь приходит другая реализация интерфейса Map, а именно TreeMap. TreeMap имплементирует интерфейс NavigableMap, который наследуется от SortedMap, а он, в свою очередь от интерфейса Map. Имплементируя интерфейсы NavigableMap и SortedMap, TreeMap получает дополнительный функционал, которого нет в HashMap, но платить за это приходится производительностью. Существует еще класс LinkedHashMap, который тоже позволяет хранить данные в определенном порядке, а именно в порядке добавления. Чтобы тебе были понятны различия между этими тремя классами, посмотри на эту таблицу: Как видишь, в этих классах есть много общего, но и есть несколько отличий. Хоть класс TreeMap является самым многофункциональным, он не всегда может хранить null в качестве ключа. Кроме этого, время доступа к элементам TreeMap будет самым длительным. Поэтому если тебе не нужно хранить данные в отсортированном виде, лучше используй HashMap или LinkedHashMap.

Когда TreeMap оправдан

Брать TreeMap стоит там, где порядок ключей это часть самой задачи:

• нужен постоянно отсортированный набор данных, а не разовая сортировка перед выводом;
• нужны запросы по диапазону: все записи от одной даты до другой, все цены выше указанной;
• нужен ближайший подходящий ключ, а не точное совпадение: тарифная сетка, границы скидок, поиск ближайшего порога;
• нужны первый и последний элементы по порядку, то есть минимум и максимум.

Во всех остальных случаях выигрывает HashMap.

Красно-черное дерево

Как ты наверняка заметил, под капотом 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/

Поиск нужного элемента идет по простому алгоритму:

1. начинаем с корня дерева, в нашем случае это 61;
2. сравниваем искомый ключ со значением текущего узла;
3. если искомое значение меньше, идем в левую сторону, если больше, в правую;
4. повторяем шаги 2 и 3, пока не найдем нужное значение или не упремся в элемент со значением null (листок дерева).

Красные и черные цвета используются для упрощения навигации по дереву и его балансировки. Существуют правила, которые всегда должны быть соблюдены при постройке красно-черного дерева:

• Корень должен быть окрашен в черный цвет.
• Листья дерева должны быть черного цвета.
• Красный узел должен иметь два черных дочерних узла.
• Черный узел может иметь любые дочерние узлы.
• Путь от узла к его листьям должен содержать одинаковое количество черных узлов.
• Новые узлы добавляются на места листьев.

Правила 3 и 5 вместе не дают дереву перекоситься: красный узел не может стоять под красным, а черных узлов на любом пути вниз поровну. Отсюда и главное свойство такого дерева: самый длинный путь от корня к листу максимум вдвое длиннее самого короткого, поэтому глубина остается порядка log n, а поиск не вырождается в перебор. Количество черных узлов на пути от узла вниз до его листьев называется “черная высота”. Красно-черное дерево реализуют на разных языках программирования. В интернете существует куча реализаций для Java, поэтому не будем на нем останавливаться надолго, а продолжим знакомство с функционалом TreeMap. Кстати, на этой же структуре построен и TreeSet: внутри он держит тот же TreeMap, только значения в нем не используются.

Методы, полученные из интерфейсов SortedMap и NavigableMap

Как и HashMap, TreeMap имплементирует интерфейс Map, а это значит, что в TreeMap есть все те методы, что и в HashMap. Но вдобавок TreeMap реализует интерфейсы SortedMap и NavigableMap, получая дополнительный функционал из них.

Методы из SortedMap

SortedMap это интерфейс, который расширяет Map и добавляет методы, актуальные для отсортированного набора данных:

• firstKey(): возвращает ключ первого элемента мапы;
• lastKey(): возвращает ключ последнего элемента;
• headMap(K end): возвращает мапу, которая содержит все элементы текущей, от начала до элемента с ключом end;
• tailMap(K start): возвращает мапу, которая содержит все элементы текущей, начиная с элемента start и до конца;
• subMap(K start, K end): возвращает мапу, которая содержит все элементы текущей, начиная с элемента start и до элемента с ключом end.

Методы из NavigableMap

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

Что изменилось в Java 21

Расклад, описанный выше, был полностью верен до Java 21. В этой версии появились Sequenced Collections (JEP 431), и монополия TreeMap на навигацию по краям коллекции закончилась. LinkedHashMap теперь реализует новый интерфейс SequencedMap, а вместе с ним получает методы firstEntry(), lastEntry(), pollFirstEntry(), pollLastEntry(), putFirst(), putLast() и reversed(). Сам TreeMap при этом ничего не потерял: SortedMap тоже стал наследником SequencedMap, так что в списке его интерфейсов просто прибавился еще один пункт. Меняется другое, а именно выбор класса. Если тебе нужны были только первый и последний элементы, а не сортировка и не поиск ближайшего ключа, то с Java 21 для этого достаточно LinkedHashMap с его доступом за O(1). Все остальное, то есть ceilingKey(), floorKey(), headMap(), tailMap() и subMap(), по-прежнему есть только у 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) {
      Comparator<Person> byAgeThenLastName = Comparator
              .comparingInt((Person p) -> p.age)
              .thenComparing(p -> p.lastName);

      TreeMap<Person, Integer> map = new TreeMap<>(byAgeThenLastName);
      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 это количество показов рекламы в этом месяце. В конструкторе передаем компаратор, который отсортирует людей по возрасту, а ровесников по фамилии. Второе условие тут не для красоты: одинаковыми TreeMap считает те ключи, для которых компаратор вернул 0, поэтому сравнение только по возрасту молча выбросило бы из мапы всех ровесников, кроме одного. Обрати внимание и на явный тип (Person p) в первой лямбде: без него компилятор не выведет тип в цепочке с thenComparing(). Заполняем map рандомными значениями. Теперь нам нужно получить ссылку на первого взрослого человека в нашем мини-хранилище данных. Делаем это с помощью Stream API. Учти, что findFirst().get() бросит NoSuchElementException, если совершеннолетних в мапе не окажется, так что в боевом коде результат стоит проверять через Optional. После этого получаем две мапы, которые передаем в методы, показывающие рекламу. Важный нюанс: headMap() и tailMap() возвращают не копию, а представление (view) исходной мапы. Данные там те же самые, и правка такого представления меняет исходную map. Существует очень много способов, которыми можно было бы решить эту задачу. Арсенал методов класса TreeMap позволяет изобретать решения на любой вкус. Запоминать их все не обязательно, ведь всегда можно воспользоваться документацией или подсказками среды разработки. На этом все! Надеюсь, теперь класс TreeMap для тебя понятен, и ты найдешь ему точное применение в решении практических задач.

Вопросы и ответы

Чем TreeMap отличается от HashMap?

HashMap хранит пары в корзинах и не гарантирует порядок, зато дает доступ за O(1). TreeMap хранит пары в красно-черном дереве, всегда держит ключи отсортированными и дает доступ за O(log n). Плюс у TreeMap есть методы навигации из интерфейсов SortedMap и NavigableMap, которых у HashMap нет.

Можно ли использовать null в качестве ключа в TreeMap?

При естественном порядке ключей нельзя: TreeMap сравнивает ключи между собой, и попытка положить null закончится NullPointerException. Такой ключ пройдет только тогда, когда в конструктор передан компаратор, умеющий сравнивать null, например построенный через Comparator.nullsFirst(). На значения ограничение не распространяется: null в качестве значения TreeMap принимает всегда.

Что будет, если компаратор считает два разных ключа равными?

Равенство ключей для TreeMap определяет результат метода compare(), а не equals(). Если компаратор вернул 0, мапа считает ключи одинаковыми, и новое значение затрет старое. Компаратор, который сравнивает людей только по возрасту, не даст положить в мапу двух ровесников. Лечится это уточнением компаратора, например сравнением по фамилии через thenComparing().

Методы headMap() и tailMap() возвращают копию или представление?

Представление. В документации Oracle такой результат называется view: он смотрит в ту же самую мапу, поэтому изменения видны в обе стороны. Если нужна независимая копия, ее придется создать самому, например new TreeMap<>(map.headMap(key)).

Какая сложность у операций TreeMap?

get(), put(), remove() и containsKey() работают за гарантированные O(log n), именно такую гарантию дает документация класса. У HashMap те же операции в среднем занимают O(1), поэтому на больших объемах данных разница заметна.

Потокобезопасен ли TreeMap?

Нет. Если с одной мапой работают несколько потоков и хотя бы один из них меняет ее состав, синхронизацию нужно обеспечивать самому. Простой вариант это обертка Collections.synchronizedSortedMap(new TreeMap<>()). Если нужны одновременно сортировка и многопоточность, берут ConcurrentSkipListMap.

Читайте также

• Подробный разбор класса HashMap
• Коллекции в Java: Java Collections Framework
• Метод compareTo в Java
• HashSet и интерфейс Set в Java