TreeMap, TreeSet и сортировка

Красно-чёрное дерево

TreeMap — это самобалансирующееся красно-чёрное дерево (разновидность бинарного дерева поиска). Балансировка через цвета узлов и повороты держит высоту порядка log n, поэтому get/put/remove — O(log n).

Главное отличие от HashMap — данные всегда упорядочены по ключу, что и даёт диапазонные операции, недоступные хеш-таблице.

NavigableMap: диапазоны и навигация

TreeMap реализует NavigableMap: floorKey/ceilingKey (ближайший не больше/не меньше), higherKey/lowerKey (строго), firstKey/lastKey, а также представления headMap/tailMap/subMap и descendingMap.

Это делает TreeMap инструментом для запросов «найти ближайшее», «всё в диапазоне», «топ-N по порядку» — там, где HashMap бессилен.

Comparable против Comparator

Порядок задаётся либо естественным (ключ реализует Comparable.compareTo), либо внешним Comparator, переданным в конструктор. Comparator гибко собирается: Comparator.comparing(...).thenComparing(...).reversed().

Важная тонкость: в TreeMap равенство определяется результатом сравнения (compareTo/compare == 0), а не equals. Если сравнение не согласовано с equals, карта будет вести себя «странно» с точки зрения контракта Map — например, два equals-различных ключа со сравнением 0 будут считаться одним.

Comparator<User> byAgeThenName =
    Comparator.comparingInt(User::age).thenComparing(User::name);
TreeMap<User, Order> m = new TreeMap<>(byAgeThenName);

Сортировка коллекций

List.sort/Collections.sort используют TimSort — стабильный адаптивный алгоритм со сложностью O(n log n), который очень быстр на частично упорядоченных данных (находит и сливает уже отсортированные «прогоны»). Стабильность означает, что равные элементы сохраняют исходный порядок.

Arrays.sort для примитивов использует dual-pivot quicksort (нестабильный, но без оверхеда на объекты). Нарушение контракта Comparator (нетранзитивное сравнение) приводит к IllegalArgumentException «Comparison method violates its general contract».

Как отвечать на собеседовании

Назовите основу (красно-чёрное дерево, O(log n)), приведите навигационные операции как причину выбора TreeMap вместо HashMap, объясните согласованность compareTo с equals и упомяните TimSort (стабильный, адаптивный) для сортировки списков.