В чем разница между HashMap и TreeMap?

Разница между HashMap и TreeMap

HashMap и TreeMap — это две основные реализации интерфейса Map в Java, которые различаются по структуре данных, производительности и гарантиям порядка элементов.

HashMap — быстрый, неупорядоченный

HashMap использует массив хеш-таблицы для хранения элементов. Основан на хеширующей функции.

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

for (String key : hashMap.keySet()) {
    System.out.println(key);
}
// Порядок непредсказуем: могут быть apple, zebra, banana

Характеристики HashMap:

• Доступ по ключу: O(1) в среднем случае
• Вставка: O(1) в среднем случае
• Удаление: O(1) в среднем случае
• Порядок элементов: не гарантирован (хаотичный)
• Позволяет null в качестве ключа и значения
• Не потокобезопасен (используй ConcurrentHashMap для многопоточности)

TreeMap — упорядоченный, медленнее

TreeMap использует красно-черное дерево для хранения элементов. Элементы отсортированы по ключам.

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

for (String key : treeMap.keySet()) {
    System.out.println(key);
}
// Порядок гарантирован: apple, banana, zebra (по алфавиту)

Характеристики TreeMap:

• Доступ по ключу: O(log n)
• Вставка: O(log n)
• Удаление: O(log n)
• Порядок элементов: гарантированный (отсортирован по ключам)
• НЕ позволяет null в качестве ключа (выбросит NullPointerException)
• Реализует SortedMap и NavigableMap интерфейсы
• Не потокобезопасен

Сравнительная таблица

Практические примеры

Пример 1: Использование HashMap для скорости

public class CacheExample {
    private Map<String, User> userCache = new HashMap<>();
    
    public void cacheUser(String id, User user) {
        userCache.put(id, user); // O(1) — очень быстро
    }
    
    public User getUser(String id) {
        return userCache.get(id); // O(1) — очень быстро
    }
}

HashMap идеален для кэшей и быстрого поиска по ключу, когда порядок не важен.

Пример 2: Использование TreeMap для сортировки

public class SortedStatistics {
    private Map<Integer, String> scores = new TreeMap<>();
    
    public void addScore(int points, String player) {
        scores.put(points, player);
    }
    
    public void printScores() {
        // Выведет в порядке возрастания очков
        scores.forEach((points, player) -> 
            System.out.println(player + ": " + points)
        );
    }
}

TreeMap полезен для лидербордов, сортировки данных, поиска диапазонов значений.

Пример 3: Поиск диапазона в TreeMap

TreeMap<Integer, String> salaries = new TreeMap<>();
salaries.put(1000, "Employee A");
salaries.put(2000, "Employee B");
salaries.put(3000, "Employee C");
salaries.put(5000, "Employee D");

// Получить все зарплаты от 1500 до 3500
Map<Integer, String> range = salaries.subMap(1500, 3500);
// Результат: {2000=Employee B, 3000=Employee C}

// Получить первые элементы
Map.Entry<Integer, String> first = salaries.firstEntry();
Map.Entry<Integer, String> last = salaries.lastEntry();

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

• Нужна максимальная скорость доступа (O(1))
• Порядок элементов не важен
• Нужна поддержка null ключей
• Большие объемы данных (больше 1000000 элементов)
• Кэширование и быстрый поиск

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

• Данные должны быть отсортированы по ключам
• Нужны операции диапазона (subMap, headMap, tailMap)
• Нужен доступ к первому/последнему элементу
• Нужен итератор в отсортированном порядке
• Меньший объем данных
• Нужна работа с SortedMap интерфейсом

Вывод

Выбор между HashMap и TreeMap зависит от требований:

• Если нужна скорость и порядок не важен → HashMap
• Если нужны отсортированные данные и операции с диапазонами → TreeMap

В большинстве случаев HashMap предпочтителен из-за лучшей производительности.