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

Основные различия между HashMap, LinkedHashMap и TreeMap

Все три класса реализуют интерфейс Map, но отличаются внутренней структурой, порядком элементов, производительностью и поддержкой null.

1. HashMap — базовая реализация

Внутренняя структура: хеш-таблица (массив + связные списки / красно-черные деревья с Java 8).

Порядок элементов: не гарантируется. Порядок может меняться при расширении таблицы.

Производительность: O(1) для get/put в среднем случае. O(n) в худшем (коллизии).

Null: допускает один null-ключ и любое количество null-значений.

Map<Integer, String> hashMap = new HashMap<>();
hashMap.put(3, "Анна");
hashMap.put(1, "Иван");
hashMap.put(2, "Мария");
hashMap.put(null, "NullKey");
System.out.println(hashMap); // {null=NullKey, 1=Иван, 2=Мария, 3=Анна}

2. LinkedHashMap — сохраняет порядок вставки

Внутренняя структура: хеш-таблица + двусвязный список.

Порядок элементов: по умолчанию — порядок вставки. Можно включить порядок доступа (access-order) через конструктор.

Производительность: O(1) для get/put, но чуть медленнее HashMap из-за поддержки списка.

Null: допускает один null-ключ и null-значения.

Map<Integer, String> linkedMap = new LinkedHashMap<>();
linkedMap.put(3, "Анна");
linkedMap.put(1, "Иван");
linkedMap.put(2, "Мария");
System.out.println(linkedMap); // {3=Анна, 1=Иван, 2=Мария} — порядок вставки сохранен

3. TreeMap — сортировка по ключам

Внутренняя структура: красно-черное дерево (самобалансирующееся бинарное дерево).

Порядок элементов: естественный порядок ключей (Comparable) или через Comparator.

Производительность: O(log n) для get/put/remove.

Null: не допускает null-ключи (NullPointerException). null-значения разрешены.

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Анна");
treeMap.put(1, "Иван");
treeMap.put(2, "Мария");
System.out.println(treeMap); // {1=Иван, 2=Мария, 3=Анна} — отсортировано по ключам

// Пример с Comparator
Map<String, String> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.put("b", "2");
reverseMap.put("a", "1");
reverseMap.put("c", "3");
System.out.println(reverseMap); // {c=3, b=2, a=1}

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

• HashMap — 90% случаев. Если порядок не важен, нужна максимальная скорость.
• LinkedHashMap — когда важен порядок вставки (например, LRU-кэш при access-order).
• TreeMap — когда нужно получать элементы в отсортированном виде (например, для диапазонных запросов: subMap, headMap).

Дополнительные возможности

LinkedHashMap можно использовать как LRU-кэш:

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // access-order = true
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

TreeMap предоставляет методы для работы с диапазонами:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "a"); map.put(3, "c"); map.put(5, "e");
System.out.println(map.subMap(2, 4)); // {3=c}
System.out.println(map.headMap(3));   // {1=a}
System.out.println(map.tailMap(3));   // {3=c, 5=e}

Итоговая таблица сравнения

Для многопоточности используйте ConcurrentHashMap или обертки Collections.synchronizedMap().

Map<String, String> safeTreeMap = new TreeMap<>((a, b) -> {
    if (a == null && b == null) return 0;
    if (a == null) return -1;
    if (b == null) return 1;
    return a.compareTo(b);
});
safeTreeMap.put(null, "nullKey");
safeTreeMap.put("b", "2");
System.out.println(safeTreeMap); // {null=nullKey, b=2}