Какие плюсы и минусы TreeMap?

Плюсы и минусы TreeMap

TreeMap — это реализация интерфейса NavigableMap, которая хранит элементы в отсортированном порядке, используя красно-черное дерево (Red-Black Tree).

Плюсы TreeMap

1. Гарантированный порядок элементов

Map<String, Integer> map = new TreeMap<>();
map.put("zebra", 1);
map.put("apple", 2);
map.put("banana", 3);

// Итерация будет в отсортированном порядке: apple, banana, zebra
for (String key : map.keySet()) {
    System.out.println(key);
}

2. Поддержка диапазонных запросов (Range Queries)

Можно эффективно получить элементы в заданном диапазоне:

SortedMap<Integer, String> map = new TreeMap<>();
map.put(1, "один");
map.put(3, "три");
map.put(5, "пять");
map.put(7, "семь");

// Получить элементы с ключами от 2 до 6
SortedMap<Integer, String> range = map.subMap(2, 7);
// Результат: {3=три, 5=пять}

3. NavigableMap методы

Доступны удобные методы для навигации:

NavigableMap<Integer, String> map = new TreeMap<>();
map.put(1, "один");
map.put(3, "три");
map.put(5, "пять");

map.lowerKey(4);        // 3
map.floorKey(4);        // 3
map.ceilingKey(4);      // 5
map.higherKey(4);       // 5
map.firstEntry();       // 1=один
map.lastEntry();        // 5=пять
map.pollFirstEntry();   // удалить и получить первый
map.pollLastEntry();    // удалить и получить последний

4. Пользовательская сортировка

Можно определить собственный компаратор:

Map<String, Integer> map = new TreeMap<>(
    Comparator.reverseOrder() // в обратном порядке
);

map.put("zebra", 1);
map.put("apple", 2);

// Итерация в обратном порядке: zebra, apple

Минусы TreeMap

1. Более медленная работа чем HashMap

Операции O(log n) вместо O(1):

// HashMap — O(1)
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("key", 1);    // быстро

// TreeMap — O(log n)
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("key", 1);    // медленнее

2. Больше использует памяти

Требует дополнительной памяти для хранения структуры красно-черного дерева:

// На 1 миллион записей TreeMap потребует больше памяти
// чем HashMap из-за структуры дерева

3. Требует сравнимые ключи

Ключи должны быть сравнимы (реализовать Comparable или передать Comparator):

// Это будет выбросить исключение
Map<Object, String> map = new TreeMap<>();
map.put(new Object(), "значение"); // ClassCastException при вставке второго элемента

// Правильно: с компаратором для не-сравнимых объектов
Map<CustomClass, String> map = new TreeMap<>((a, b) -> 
    Integer.compare(a.id, b.id)
);

4. Не потокобезопасная

Нужно синхронизировать вручную для многопоточной работы:

Map<String, Integer> map = Collections.synchronizedSortedMap(
    new TreeMap<>()
);

5. Не может содержать null ключей

В отличие от HashMap:

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 1); // NullPointerException

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put(null, 1); // Работает

Сравнение с HashMap

Когда использовать TreeMap

• Когда нужен отсортированный порядок элементов
• Когда требуются диапазонные запросы (subMap, headMap, tailMap)
• Когда нужна навигация по ключам (lower, floor, ceiling, higher)
• Когда количество элементов небольшое, и производительность некритична

Когда использовать HashMap

• Когда нужна максимальная скорость доступа O(1)
• Когда порядок элементов не важен
• Когда работа с большим количеством элементов
• Когда нужна поддержка null ключей