Что такое TreeMap в Java и каковы его ключевые особенности?

TreeMap — это реализация интерфейса SortedMap (и, как следствие, NavigableMap) в Java, которая хранит пары ключ-значение в отсортированном по ключам порядке.

Ключевые особенности:

• Сортировка: Элементы автоматически сортируются по их естественному порядку (ключи должны реализовывать Comparable) или с помощью переданного Comparator.
• Основа: Реализована на основе красно-черного дерева (Red-Black Tree), что гарантирует логарифмическое время O(log n) для основных операций (put, get, remove).
• Упорядоченность: Позволяет эффективно выполнять операции с "подмножествами" (например, subMap, headMap, tailMap).
• Не синхронизирована: Как и большинство коллекций, TreeMap не потокобезопасна.

Пример использования:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");

// Элементы выводятся в отсортированном порядке по ключу
System.out.println(map); // {1=One, 2=Two, 3=Three}

// Получение первого и последнего ключа
System.out.println(map.firstKey()); // 1
System.out.println(map.lastKey());  // 3

Сравнение с HashMap: HashMap обеспечивает константное время O(1) для операций, но не поддерживает порядок. TreeMap медленнее, но предоставляет упорядоченность.