Ответ
TreeMap и HashMap — это реализации интерфейса Map, но с фундаментально разной внутренней структурой и гарантиями.
| Характеристика | HashMap | TreeMap |
|---|---|---|
| Внутренняя структура | Хэш-таблица (массив + связные списки / деревья) | Красно-черное дерево (сбалансированное бинарное дерево поиска) |
| Порядок элементов | Не гарантируется. Может меняться при рехешинге. | Элементы отсортированы по ключам (естественный порядок или Comparator). |
| Временная сложность (put/get) | O(1) в среднем, O(n) в худшем случае (коллизии) |
O(log n) гарантированно для основных операций. |
| Допустимые ключи | Должны корректно реализовывать hashCode() и equals(). |
Должны быть Comparable или нужен внешний Comparator. |
| Дополнительные операции | - | firstKey(), lastKey(), subMap(), headMap(), tailMap() (диапазонные запросы). |
Пример использования TreeMap:
TreeMap<Integer, String> scoreboard = new TreeMap<>(Comparator.reverseOrder());
scoreboard.put(150, "Alice");
scoreboard.put(95, "Bob");
scoreboard.put(120, "Charlie");
System.out.println(scoreboard); // {150=Alice, 120=Charlie, 95=Bob} (по убыванию ключа)
System.out.println("Top scorer: " + scoreboard.firstEntry()); // Top scorer: 150=Alice
// Получить всех, кто набрал от 100 до 200 очков
Map<Integer, String> topPlayers = scoreboard.subMap(200, 100);Когда использовать TreeMap:
- Когда критически важен порядок элементов по ключу (например, вывод отсортированных данных, работа с диапазонами).
- Когда нужны гарантии производительности
O(log n), а не средний случайO(1)с риском деградации доO(n)вHashMap. - Когда необходимы операции с навигацией по отсортированным ключам (поиск ближайшего, получение подмножества).
В большинстве других случаев HashMap предпочтительнее из-за своей средней константной скорости.