Class TreeMap
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey , get , put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.
Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare ) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals ; it just fails to obey the general contract of the Map interface.
Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be «wrapped» using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(. ));
The iterators returned by the iterator method of the collections returned by all of this class’s «collection view methods» are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put .)
This class is a member of the Java Collections Framework.
TreeMap в Java — особенности и использование
Класс TreeMap входит в состав Java Collection Framework и представляет собой структуру данных в виде дерева. Разберемся, как устроен и когда стоит применять. Особенность TreeMap — ключи хранятся в отсортированном порядке и сложность поиска ключа составляет O(log n).
Используется в примерах Java версии 17
Иерархия наследования TreeMap #
Класс TreeMap наследует интерфейс NavigableMap и расширяет абстрактный класс AbstractMap.
NavigableMap обязывает класс реализовать методы, часть из которых:
- Map.Entry firstEntry() — получение записи Entry с наименьшим ключом.
- Map.Entry lastEntry() — получение записи Entry с наибольшим ключом.
- Map.Entry pollFirstEntry() — возвращает запись Entry с наименьшим ключом и удаляет из TreeMap.
- Map.Entry pollLastEntry() — возвращает запись Entry с наибольшим ключом и удаляет из TreeMap.
- NavigableMap descendingMap() — возвращает Map в обратном направлении, изменения в возвращаемом Map напрямую влияет на исходную TreeMap
- K lowerKey(K key) — получение первого ключа, точно меньше по значению чем переданный ключ или null, если такого ключа не найдено
- K higherKey(K key) — получение первого ключа, точно больше по значению чем переданный ключ или null, если такого ключа не найдено
Остальные методы похожи на представленные в списке или имеют вариации.
Класс AbstractMap уже имеет часть реализаций интерфейса Map , например int size() , boolean isEmpty() , boolean containsValue(Object value) , boolean containsKey(Object key) и другие. Причем, часть из них TreeMap переопределяет для реализации своей структуры.
Особенности TreeMap #
Перед погружением в структуру класса, рассмотрим — “Что делает TreeMap особенным и когда стоит его использовать?”
Стоит использовать TreeMap, в случае если вам требуется быстро извлекать данные по ключу, при этом требуется сортировка по ключу. Например, если вам необходимо получать минимальный или максимальный ключ или получать набор данных меньше или больше определенного ключа.
Если обратиться к более конкретным примерам:
- необходимо хранить строки-ключи в алфавитном порядке, ключ String.
- расположить объекты по приоритету, но получать по ключу. Первую часть у нас может решить TreeSet, но получать по ключу мы не можем.
- хранить объекты в разных TreeMap, с разной сортировкой.
Воспользоваться всеми преимуществами TreeMap возможно, если объявлять тип не просто Map, а NavigableMap или TreeMap
Записать слова Zeta, Asteroid, back, Art, Bow, zen в списки по первой букве:
a=[Asteroid, Art], b=[back, Bow], z=[Zeta, zen]> 3=[Art, Bow, zen], 4=[Zeta, back], 8=[Asteroid]> Таким образом, мы можем быстро получить все слова на букву B или все слова, в которых количество букв больше 3.
Код реализующий пример выше:
String[] words = "Zeta", "Asteroid", "back", "Art", "Bow", "zen" >; // создаем TreeMap и заполняем словами, ключ для каждого - первая буква // используем в объявлении типа именно NavigableMap, так как нам нужны будут // его уникальные методы NavigableMapCharacter, ListString>> wordsByFirstLetter = new TreeMap<>(); for (String s : words) wordsByFirstLetter .computeIfAbsent(s.toLowerCase().charAt(0), ArrayList::new) .add(s); > System.out.println(wordsByFirstLetter); // Все слова на букву b System.out.println(wordsByFirstLetter.get('b')); // создаем TreeMap и заполняем словами, ключ для каждого - длина слова // используем в объявлении типа именно NavigableMap, так как нам нужны будут // его уникальные методы NavigableMapInteger, ListString>> stringsBySize = new TreeMap<>(); for (String s : words) stringsBySize.computeIfAbsent(s.length(), ArrayList::new).add(s); > System.out.println(stringsBySize); // Получим все слова длиной больше или равные 4 и сведем в один список ListString> wordsLengthGtThree = stringsBySize.tailMap(4) .values() .stream() .flatMap(Collection::stream) .toList(); System.out.println(wordsLengthGtThree); [back, Bow] [Zeta, back, Asteroid] Что внутри TreeMap? #
Для этого зайдем в исходный код самого класса и найдем, что он хранит в полях:
- Компаратор — неудивительно, ведь нам нужны правила для сравнения ключей и расположения их в нужном порядке.
private final Comparator super K> comparator private transient EntryK,V> root private transient int size = 0 - счетчик изменений коллекции, используется для определения попытки изменить TreeMap несколькими потоками. Если такое будет замечено — получим ConcurrentModificationException
private transient int modCount = 0 Больше ничего и нет в TreeMap, если не учитывать size и modCount — ведь они не несут полезной информации. То в TreeMap есть только компаратор и ссылка на корневой элемент дерева.
И скорее вы уже слышали, что в TreeMap используется красно-черное дерево. Давай посмотрим наглядно, что происходит, когда мы создаем TreeMap и наполняем его элементами. Будем использовать наш пример со словами.
Конструкторы #
Первое что нам нужно — создать новый TreeMap . Какие у нас есть конструкторы для этого?
var wordsByLength = new TreeMapInteger, String>(); После его создания внутри класса comparator=null , root=null , size=0 , modCount=0 . Полностью пустой класс. Пустым конструктором можно пользоваться, если класс ключа реализует интерфейс Comparable , который делаем возможным сравнить два объекта класса и расставить их по порядку. Класс Integer наследует Comparable и мы можем его использовать как ключ без дополнительных настроек.
record Planet(String name, long radius) <> var populationByPlanet = new TreeMapPlanet, Long>( Comparator.comparing(Planet::radius)); После создания, снова заглянем внутрь TreeMap и увидим: comparator=Comparator$lambda@716 , root=null , size=0 , modCount=0 . Мы передали компаратор в виде лямбды и видим — класс знает в каком порядку расположить планеты. Можно заполнять планетами и они будут расположены в порядке роста радиуса.
🌟 Больше про компараторы и варианты сортировки — в моей статье “Сортировка в Java”
var treeMap = new TreeMap<>(Map.of(8, "Oxygen", 75, "Rhenium")); Integer известно как сравнивать — компаратор не понадобится. И в итоге в объекте comparator=null , root=TreeMap$Entry , size=2 , modCount=2 .
В конструкторе произошло добавление элементов, поэтому видим — корневой элемент уже не пустой, было 2 модификации и количество элементов равно 2. Пока достаточно того, что у нас данные из Map перенеслись в TreeMap . Дальше мы будем смотреть как они располагаются.
Фактически это конструктор принимающий другую TreeMap , так как TreeMap это наследник SortedMap . При этом копируется значение comparator и все элементы переносятся во вновь созданный TreeMap .
var treeMap = new TreeMap<>(Map.of(8, "Oxygen", 75, "Rhenium")); var subTreeMap = new TreeMap<>(treeMap.subMap(10, 100)); В subTreeMap будет один элемент «Rhenium»> . Если мы просто сохранили результат метода treeMap.subMap(10, 100) , то получили SortedMap , а не TreeMap .
Заключение #
В этой небольшой статье было показано какие особенности есть у TreeMap и в каких случаях его стоит применять.