Какое дерево используется в TreeMap?

Что проверяют

Знаете ли вы, что под TreeMap лежит красно-чёрное дерево, и понимаете ли, что из этого следует для сложности и порядка ключей. Следом часто спрашивают, почему не AVL и где ещё в JDK встречаются такие деревья.

Как отвечать

TreeMap это реализация NavigableMap на красно-чёрном дереве, самобалансирующемся двоичном дереве поиска. Правила раскраски (корень чёрный, у красного узла дети чёрные, на любом пути вниз одинаковое число чёрных узлов) держат высоту не больше примерно 2·log(n). Отсюда get, put, remove, containsKey за O(log n).

Дальше стоит сказать:

• порядок: ключи сравниваются через Comparable или переданный Comparator, equals не участвует. Если compare вернул 0, ключи считаются одинаковыми и значение перезапишется;
• null-ключ: при естественном порядке put(null, ...) бросает NullPointerException, с компаратором, который умеет null, это допустимо;
• навигация: firstKey, floorKey, ceilingKey, higherKey, диапазоны subMap, headMap, tailMap, descendingMap. Ради этого TreeMap обычно и берут;
• почему не AVL: AVL сбалансировано строже и ищет чуть быстрее, но при изменениях делает больше поворотов. Красно-чёрному хватает не больше двух поворотов на вставку и трёх на удаление;
• где ещё: TreeSet построен поверх TreeMap, а HashMap с Java 8 превращает переполненную корзину в красно-чёрное дерево, когда цепочка перерастает порог в 8 элементов и в таблице не меньше 64 корзин.

TreeMap не синхронизирован. Конкурентный отсортированный словарь это ConcurrentSkipListMap, он построен на списке с пропусками, а не на дереве.

Где спотыкаются

Отвечают «бинарное дерево поиска» без слова о балансировке. Обычное BST на отсортированной вставке вырождается в список с O(n).

Пишут компаратор, несогласованный с equals, например сравнивают пользователей только по возрасту. Два разных человека одного возраста становятся одним ключом, и данные тихо теряются.

Путают структуры: говорят, что HashMap целиком становится деревом, или что TreeMap построен на B-дереве.