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

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

Краткое описание

Оба класса — это реализации интерфейса Map в Java, но отличаются порядком хранения и обхода элементов.

HashMap

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

• Не гарантирует порядок элементов
• Основан на хеш-таблице
• Итерация происходит в произвольном порядке
• Использует массив с разрешением коллизий через цепочки (linked lists) или красно-чёрные деревья (в Java 8+)
• Быстрее по памяти (нет дополнительных указателей)

Пример:

Map<String, String> map = new HashMap<>();
map.put("apple", "яблоко");
map.put("banana", "банан");
map.put("cherry", "вишня");

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

LinkedHashMap

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

• Гарантирует порядок вставки (insertion order)
• Наследует HashMap и добавляет двусвязный список (doubly-linked list)
• Каждая запись содержит ссылки на предыдущую и следующую запись
• Итерация в порядке добавления элементов
• Немного медленнее и требует больше памяти (дополнительные указатели)
• Может быть настроен для LRU (Least Recently Used) кэша с параметром accessOrder

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

Map<String, String> map = new LinkedHashMap<>();
map.put("apple", "яблоко");
map.put("banana", "банан");
map.put("cherry", "вишня");

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

LRU режим (Access Order):

// LinkedHashMap с accessOrder=true (порядок доступа, не вставки)
LinkedHashMap<String, String> lruMap = new LinkedHashMap<String, String>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 3; // Максимум 3 элемента
    }
};

lruMap.put("a", "value_a");
lruMap.put("b", "value_b");
lruMap.put("c", "value_c");

System.out.println(lruMap.keySet()); // [a, b, c]

lruMap.get("a"); // Получаем "a", он становится "самым свежим"

System.out.println(lruMap.keySet()); // [b, c, a]

lruMap.put("d", "value_d"); // Добавляем 4-й элемент

System.out.println(lruMap.keySet()); // [c, a, d] - "b" удалился как самый старый

Структура памяти

HashMap:

Array of buckets:
[0] -> Node(hash, key, value) -> Node -> ...
[1] -> null
[2] -> Node(hash, key, value)
...

LinkedHashMap:

Array of buckets: (как HashMap)
[0] -> Node(hash, key, value) -> Node -> ...
[1] -> null
[2] -> Node(hash, key, value)
...

Дополнительно: двусвязный список
head <-> Node1 <-> Node2 <-> Node3 <-> tail

Сравнение

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

HashMap:

• Когда порядок элементов не важен
• Максимальная производительность
• Обычные кеши и словари
• Когда нужна максимальная экономия памяти

LinkedHashMap:

• Когда нужно сохранить порядок вставки
• Реализация LRU кэша
• Логирование или трассировка (с сохранением последовательности)
• JSON сериализация (сохранение порядка ключей)
• Когда нужно знать, в каком порядке были добавлены элементы

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

Пример 1: Простой порядок

Map<String, Integer> users = new LinkedHashMap<>();
users.put("Alice", 30);
users.put("Bob", 25);
users.put("Charlie", 35);

// Всегда выведет в порядке добавления
users.forEach((name, age) -> System.out.println(name + ": " + age));

Пример 2: LRU кэш

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

var cache = new LRUCache<String, String>(2);
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.get("key1"); // key1 становится самым свежим
cache.put("key3", "value3"); // key2 будет удалён

Пример 3: JSON с сохранением порядка

// Часто LinkedHashMap используют для парсинга JSON
Map<String, Object> jsonData = new LinkedHashMap<>();
jsonData.put("name", "John");
jsonData.put("age", 30);
jsonData.put("email", "john@example.com");

// При сериализации порядок сохранится

Вывод

HashMap — быстрая и экономная, но порядок не гарантирован. LinkedHashMap — гарантирует порядок вставки и позволяет реализовать LRU логику, но требует немного больше памяти. Выбирайте HashMap по умолчанию, используйте LinkedHashMap когда порядок важен.