Ответ
HashMap и TreeMap — реализации интерфейса Map, но с фундаментальными отличиями в структуре данных и поведении.
| Критерий | HashMap | TreeMap |
|---|---|---|
| Структура данных | Хеш-таблица (массив + связные списки/деревья) | Красно-черное дерево (сбалансированное бинарное дерево поиска) |
| Порядок элементов | Не гарантируется | Ключи отсортированы по естественному порядку (Comparable) или заданному Comparator |
Временная сложность put()/get() |
O(1) в среднем, O(n) в худшем случае (коллизии) | O(log n) гарантированно |
| Допустимые ключи | Разрешает один null-ключ и множество null-значений |
Не допускает null-ключи (выбрасывает NullPointerException) |
| Потокобезопасность | Нет (используйте ConcurrentHashMap) |
Нет |
Почему это важно?
- Используйте HashMap, когда нужен максимально быстрый доступ по ключу и порядок не важен.
- Используйте TreeMap, когда требуется итерирование по ключам в отсортированном порядке.
Пример:
// HashMap — порядок вставки не сохраняется
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Zebra", 3);
hashMap.put("Apple", 1);
System.out.println(hashMap); // Может вывести: {Apple=1, Zebra=3} или {Zebra=3, Apple=1}
// TreeMap — автоматическая сортировка по ключу
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Zebra", 3);
treeMap.put("Apple", 1);
System.out.println(treeMap); // Всегда выведет: {Apple=1, Zebra=3}