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

# HashMap, LinkedHashMap и TreeMap: полное сравнение

Эти три реализации Map интерфейса имеют разные характеристики производительности и гарантии порядка элементов. Понимание различий критично для выбора правильной структуры данных.

HashMap

HashMap - это реализация Map на основе хеш-таблицы. Не гарантирует порядок элементов.

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

• На основе хеширования (bucket array)
• O(1) средняя временная сложность для get/put/remove
• Не упорядочена
• Позволяет null ключ и null значения
• Не синхронизирована (использование ConcurrentHashMap для многопоточности)
• Лучшая производительность для большинства случаев

Пример использования:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
map.put("cherry", 8);
map.put(null, 0); // Допустимо

System.out.println(map.get("apple")); // 5
System.out.println(map); // Порядок случайный {cherry=8, banana=3, apple=5}

Внутренняя структура:

/*
Исходная емкость: 16 buckets
При добавлении элементов выше load factor (0.75) происходит resize

Внутри каждого bucket может быть цепочка элементов (collision chain)
или красно-черное дерево при большом количестве коллизий (Java 8+)
*/

Преимущества:

• Самая высокая производительность - O(1)
• Простая в использовании
• Эффективна по памяти
• Поддерживает null
• Идеальна для кеширования

Недостатки:

• Не гарантирует порядок элементов
• Не синхронизирована
• При большом количестве коллизий может деградировать до O(n)

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

• Кеширование
• Поиск по ключу
• Счетчики
• Когда порядок не важен

LinkedHashMap

LinkedHashMap комбинирует HashMap с двусвязным списком для сохранения порядка вставки элементов.

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

• Наследует HashMap
• Поддерживает порядок вставки (insertion order)
• O(1) для get/put/remove
• Может работать в режиме LRU (Least Recently Used)
• Позволяет null ключ и значения
• Чуть медленнее HashMap из-за поддержки списка

Пример использования:

Map<String, Integer> map = new LinkedHashMap<>();
map.put("apple", 5);
map.put("banana", 3);
map.put("cherry", 8);
map.put("apple", 10); // Обновление

System.out.println(map);
// Выведет: {apple=10, banana=3, cherry=8}
// Порядок вставки сохранен (apple был первым, остался на месте)

// Итерация в порядке вставки
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

LRU Cache пример (режим access-order):

// Режим Last-Recently-Used
LinkedHashMap<String, Integer> lruCache = 
    new LinkedHashMap<String, Integer>(16, 0.75f, true) {
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > 100; // Максимум 100 элементов
        }
    };

lruCache.put("key1", 1);
lruCache.put("key2", 2);
lruCache.get("key1"); // key1 становится самым свежим
lruCache.put("key3", 3); // key1 в конце, key2 в начале

Внутренняя структура:

/*
У каждого элемента есть:
- Ссылка на предыдущий элемент (before)
- Ссылка на следующий элемент (after)
- Значение в HashMap

Это создает двусвязный список параллельно HashMap
*/

Преимущества:

• Сохраняет порядок вставки
• Может работать в режиме LRU
• Быстрая O(1) производительность
• Предсказуемый порядок итерации
• Идеальна для кеша LRU

Недостатки:

• Немного медленнее HashMap (поддержка списка)
• Больше памяти (дополнительные ссылки before/after)
• Не сортирует по значениям

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

• LRU кэши
• Когда нужен порядок вставки
• Сессионные данные
• История операций

TreeMap

TreeMap реализует NavigableMap на основе красно-черного дерева (self-balancing BST).

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

• На основе красно-черного дерева
• O(log n) для get/put/remove
• Отсортирована по ключам
• Естественный порядок или custom Comparator
• Не позволяет null ключи (хотя значения могут быть null)
• Синхронизированная версия: Collections.synchronizedSortedMap()

Пример использования:

Map<String, Integer> map = new TreeMap<>();
map.put("cherry", 8);
map.put("apple", 5);
map.put("banana", 3);

System.out.println(map);
// Выведет: {apple=5, banana=3, cherry=8}
// Отсортировано по ключам в алфавитном порядке

// Получение первого и последнего ключа
NavigableMap<String, Integer> navMap = (NavigableMap<String, Integer>) map;
System.out.println(navMap.firstKey()); // apple
System.out.println(navMap.lastKey());  // cherry

// Диапазонные операции
Map<String, Integer> range = navMap.subMap("apple", "cherry");
// {apple=5, banana=3}

Custom Comparator:

// Сортировка по длине ключа (строки)
Map<String, Integer> map = new TreeMap<>(
    Comparator.comparingInt(String::length)
        .thenComparing(String::compareTo)
);

map.put("a", 1);
map.put("cat", 2);
map.put("apple", 3);
map.put("dog", 4);

System.out.println(map);
// {a=1, cat=2, dog=4, apple=3}
// Сортировано по длине, потом по алфавиту

Навигационные операции:

NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(20, "twenty");
map.put(30, "thirty");
map.put(40, "forty");

// Нахождение значения >= 25
Map.Entry<Integer, String> entry = map.ceilingEntry(25);
System.out.println(entry); // 30=thirty

// Нахождение значения < 25
entry = map.lowerEntry(25);
System.out.println(entry); // 20=twenty

// Диапазон
SortedMap<Integer, String> range = map.subMap(15, 35);
System.out.println(range); // {20=twenty, 30=thirty}

Таблица сравнения

Практический пример: выбор правильной Map

public class MapUsageExample {
    
    // 1. HashMap для обычного кеширования
    private Map<String, CachedData> cache = new HashMap<>();
    
    // 2. LinkedHashMap для LRU кеша
    private LinkedHashMap<String, Session> sessions = 
        new LinkedHashMap<String, Session>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > 1000; // Максимум 1000 сессий
            }
        };
    
    // 3. TreeMap для отсортированных данных
    private NavigableMap<Long, Event> events = new TreeMap<>();
    
    public void example() {
        // HashMap - быстрый поиск
        cache.put("user:123", new CachedData());
        CachedData data = cache.get("user:123");
        
        // LinkedHashMap - сохраняет порядок, может быть LRU
        sessions.put("session:abc", new Session());
        // Автоматически удалит старую сессию при превышении лимита
        
        // TreeMap - отсортирован по времени
        events.put(System.currentTimeMillis(), new Event());
        Event firstEvent = events.firstEntry().getValue();
        List<Event> recentEvents = events.tailMap(
            System.currentTimeMillis() - 3600000
        ).values().stream().toList();
    }
}

Когда использовать каждую

HashMap:

• Кеширование
• Поиск по ключу
• Счетчики объектов
• Конфигурационные данные
• Быстрый доступ где порядок не важен

LinkedHashMap:

• LRU кэши
• История операций
• Когда нужен insertion order
• Сессии с последним доступом
• Упорядоченные данные при сохранении O(1) скорости

TreeMap:

• Сортированные данные
• Диапазонные запросы
• Автоматическая сортировка
• Когда нужны операции: firstEntry, lastEntry, subMap
• Конкурентный доступ (SortedMap с синхронизацией)

Заключение

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

• Нужна максимальная скорость? HashMap
• Нужен порядок вставки или LRU? LinkedHashMap
• Нужны отсортированные данные и диапазоны? TreeMap