Если ты читаешь эту статью, скорее всего, ты знаком с интерфейсом Map и вариантами его применения. Если нет, то тебе сюда. Сегодня мы поговорим об особенностях реализации TreeMap, а конкретнее — чем она отличается от HashMap и как правильно ее использовать.
Как видишь, в этих классах есть много общего, но и есть несколько отличий. Хоть класс Поиск нужного элемента начинается из корня дерева, в нашем случае это 61. Дальше происходит сравнение с необходимым значением. Если наше значение меньше — отправляемся в левую сторону, если больше — в правую. Так происходит до тех пор, пока не найдем необходимое значение или не упремся в элемент со значением
Сравнение 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
является самым многофункциональным, он не всегда может хранить 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/
null
(листок дерева). Красные и черные цвета используются для упрощения навигации по дереву и его балансировки. Существуют правила, которые всегда должны быть соблюдены при постройке красно-черного дерева:
- Корень должен быть окрашен в черный цвет.
- Листья дерева должны быть черного цвета.
- Красный узел должен иметь два черных дочерних узла.
- Черный узел может иметь любые дочерние узлы.
- Путь от узла к его листьям должен содержать одинаковое количество черных узлов.
- Новые узлы добавляются на места листьев.
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
для тебя понятен, и ты найдешь ему точное применение в решении практических задач.