Класс TreeMap<K,​V>

public class TreeMap<K,V>
extends AbstractMap<K,​V>
implements NavigableMap<K,​V>, Cloneable, Serializable

Реализация NavigableMap на основе красно-черного дерева. Карта отсортирована в соответствии с естественным порядком своих ключей или с помощью Comparator, предоставленного во время создания карты, в зависимости от используемого конструктора.

Эта реализация гарантирует затраты времени log(n) для операций containsKey, get, put и remove. Алгоритмы являются адаптациями алгоритмов из книги Кормена, Лейзерсона и Ривеста «Введение в алгоритмы».

Обратите внимание, что порядок, поддерживаемый картой дерева, как и любой отсортированной картой, и независимо от того, предоставлен ли явный компаратор, должен быть совместимым с equals, если эта отсортированная карта должна правильно реализовать интерфейс Map. (См. Comparable или Comparator для точного определения совместимости с equals.) Это связано с тем, что интерфейс Map определен в терминах операции equals, но отсортированная карта выполняет все сравнения ключей, используя свой метод compareTo (или compare), поэтому два ключа, считающиеся равными этим методом, с точки зрения отсортированной карты, равны. Поведение отсортированной карты определено даже если её порядок несовместим с equals; оно просто не подчиняется общему контракту интерфейса Map.

Обратите внимание, что эта реализация не синхронизирована. Если несколько потоков одновременно обращаются к карте, и по крайней мере один из потоков структурно изменяет карту, она должна быть синхронизирована внешним образом. (Структурное изменение — это любая операция, которая добавляет или удаляет одну или несколько сопоставлений; простое изменение значения, связанного с существующим ключом, не является структурным изменением.) Обычно это достигается путём синхронизации на некотором объекте, естественным образом encapsulating карту. Если такого объекта нет, карта должна быть «упакована» с помощью метода Collections.synchronizedSortedMap. Это лучше всего сделать на этапе создания, чтобы предотвратить случайный несинхронизированный доступ к карте:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Итераторы, возвращаемые методом iterator коллекций, возвращаемых всеми методами «представления коллекций» этого класса, являются быстродействующими: если карта структурно изменяется в любое время после создания итератора, каким-либо способом, кроме метода самого итератора remove, итератор выбросит исключение ConcurrentModificationException. Таким образом, при одновременном изменении итератор быстро и чисто завершается, а не рискует произвольным, непредсказуемым поведением в неопределенное время в будущем.

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

Все пары Map.Entry , возвращаемые методами этого класса и его представлений, представляют собой снимки сопоставлений на момент их создания. Они не поддерживают метод Entry.setValue. (Однако, изменение сопоставлений в связанной карте возможно с использованием put.)

Этот класс является членом Java Collections Framework.