Краткий ответ

TreeMap подходит лучше, потому что хранит ключи в отсортированном порядке и поддерживает диапазонные представления через операции NavigableMap. У HashMap нет упорядоченности и эффективного механизма поиска диапазона: обычно пришлось бы просматривать все записи или отдельно сортировать ключи.

Исторический контекст

Хеш-таблицы появились как способ быстро находить значение по точному ключу, когда порядок ключей не важен. Деревья поиска решают другую задачу: сохраняют элементы в порядке сравнения и позволяют находить ближайшие, минимальные, максимальные и диапазонные значения.

TreeMap использует сбалансированное дерево поиска. Такой подход жертвует постоянным средним временем точечного доступа ради упорядоченных операций, которых у обычной хеш-таблицы нет.

Постановка проблемы

Предположим, приложению нужно получить все записи с ключами от одного значения до другого, найти ближайший ключ или обработать записи в отсортированном порядке. Выбор HashMap заставит реализовывать сортировку и фильтрацию отдельно, что увеличит сложность и риск ошибок.

Если выбрать TreeMap там, где нужны только точечные обращения, можно без необходимости получить дополнительные затраты по памяти и времени. Поэтому выбор зависит от характера операций, а не только от привычной асимптотики доступа по ключу.

Подробное решение

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

Ключи обходятся в порядке, заданном естественным сравнением или переданным Comparator. Благодаря этому операции firstKey, lastKey, ceilingKey, floorKey, а также получение диапазонов через subMap, headMap и tailMap выполняются за O(log n) для поиска границы, после чего обход найденного диапазона занимает O(k), где k — число возвращаемых записей.

Минимальный пример:

import java.util.NavigableMap;
import java.util.TreeMap;

NavigableMap<Integer, String> prices = new TreeMap<>();
prices.put(10, "low");
prices.put(20, "middle");
prices.put(30, "high");

for (var entry : prices.subMap(10, true, 30, false).entrySet()) {
    System.out.println(entry);
}

В примере диапазон выбирается непосредственно из упорядоченной структуры. Представление subMap связано с исходной картой, поэтому изменения через него отражаются в исходной коллекции; это не независимая копия.

У HashMap точечные get и put обычно имеют амортизированную сложность O(1), но порядок обхода не является контрактом. Для диапазона в ней нет операции, аналогичной subMap: полный просмотр занимает O(n), а сортировка найденных ключей — дополнительные затраты порядка O(n log n).

У TreeMap есть ограничения. Сравнение ключей должно быть согласованным с ожидаемой семантикой равенства: если компаратор возвращает ноль для двух объектов, карта считает их одним ключом, даже если equals возвращает false. Кроме того, операции дерева обычно медленнее точечного доступа к хорошо распределённой хеш-таблице из-за сравнений и переходов по узлам.

Ситуация из практики

В сервисе цен нужно было регулярно получать товары в ценовом диапазоне и находить ближайшую доступную цену. Рассматривались HashMap с последующей сортировкой ключей и TreeMap.

Вариант с HashMap был прост для точечного поиска, но каждый диапазонный запрос требовал полного обхода, а сортировка делала задержку зависимой от общего числа товаров. Дополнительная структура отсортированных ключей усложнила бы синхронизацию данных.

Был выбран TreeMap, потому что диапазонные запросы являлись основной операцией. Точечные операции стали логарифмическими вместо среднего постоянного времени, зато границы диапазона находились быстро, а результаты обходились сразу в нужном порядке без полной пересортировки.

Что кандидаты часто упускают

1. Всегда ли диапазонный запрос через TreeMap имеет сложность O(log n)?

Нет. Поиск начала диапазона занимает O(log n), но выдача k элементов требует ещё O(k). Поэтому корректная оценка обычно выглядит как O(log n + k), а не просто O(log n). Если диапазон охватывает почти всю карту, стоимость обхода будет близка к O(n).

2. Можно ли использовать TreeMap с ключами, у которых нет естественного порядка?

Да, если при создании карты передан совместимый Comparator. Без естественного сравнения и без компаратора операции, требующие сравнения ключей, не смогут корректно работать; на практике ключи должны быть взаимно сравнимыми выбранным способом.

3. Почему TreeMap может потерять одну из двух записей с разными объектами-ключами?

Потому что уникальность ключей в TreeMap определяется результатом сравнения, а не только equals. Если компаратор возвращает ноль, второй ключ считается эквивалентным первому, и его значение заменяет прежнее. Поэтому компаратор должен отражать требуемую идентичность ключей и, желательно, быть согласованным с equals.