Чем отличается HashMap от LinkedHashMap?

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

HashMap: порядок не гарантирован

HashMap хранит пары ключ-значение в хеш-таблице. При итерации по его элементам (например, через keySet(), values() или entrySet()) порядок вывода может быть любым и может меняться при добавлении новых элементов, так как зависит от хеш-кодов ключей и внутренней реструктуризации (rehashing). Это обеспечивает высокую производительность операций put() и get() (в среднем O(1)), но порядок непредсказуем.

LinkedHashMap: предсказуемый порядок

LinkedHashMap расширяет HashMap, добавляя двусвязный список, который соединяет все записи. Это позволяет сохранять порядок итерации. По умолчанию используется порядок вставки (insertion-order): элементы возвращаются в том порядке, в котором они были добавлены в карту. Также можно создать LinkedHashMap с флагом доступа (access-order), тогда порядок будет меняться при обращении к элементам (get или put), перемещая последний использованный элемент в конец, что полезно для реализации кэшей (например, LRU).

Пример кода

import java.util.*;

public class MapExample {
    public static void main(String[] args) {
        // HashMap - порядок не гарантирован
        Map hashMap = new HashMap<>();
        hashMap.put("zebra", 1);
        hashMap.put("apple", 2);
        hashMap.put("banana", 3);
        System.out.println("HashMap order: " + hashMap.keySet());
        // Может вывести: [banana, zebra, apple] или другой порядок

        // LinkedHashMap - сохраняет порядок вставки
        Map linkedMap = new LinkedHashMap<>();
        linkedMap.put("zebra", 1);
        linkedMap.put("apple", 2);
        linkedMap.put("banana", 3);
        System.out.println("LinkedHashMap order: " + linkedMap.keySet());
        // Всегда выведет: [zebra, apple, banana]

        // LinkedHashMap с access-order (LRU поведение)
        Map lruMap = new LinkedHashMap<>(16, 0.75f, true);
        lruMap.put("a", 1);
        lruMap.put("b", 2);
        lruMap.put("c", 3);
        lruMap.get("a"); // Обращение к 'a' перемещает её в конец
        System.out.println("LRU order: " + lruMap.keySet());
        // Выведет: [b, c, a]
    }
}

Производительность и использование

LinkedHashMap требует немного больше памяти из-за поддержания связного списка, но операции put, get, remove остаются константными в среднем (O(1)). Его стоит выбирать, когда важен предсказуемый порядок итерации, например, для построения кэшей с политикой вытеснения (LRU), сохранения порядка конфигурационных параметров или отображения элементов в UI в порядке добавления. Если порядок не важен, HashMap будет немного эффективнее.

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