Какой наследник Map позволяет сохранить порядок вставки?

LinkedHashMap — Сохранение Порядка Вставки в Java

Основной Ответ

LinkedHashMap — это наследник HashMap, который сохраняет порядок вставки элементов. Это одна из самых полезных структур данных в Java, которую часто забывают.

HashMap vs LinkedHashMap vs TreeMap

// HashMap — БЕЗ гарантии порядка
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 1);
hashMap.put("banana", 2);
hashMap.put("cherry", 3);
// Порядок может быть: banana, cherry, apple (случайный!)
for (String key : hashMap.keySet()) {
    System.out.println(key); // Непредсказуемо
}

// LinkedHashMap — СОХРАНЯЕТ порядок вставки
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("apple", 1);
linkedMap.put("banana", 2);
linkedMap.put("cherry", 3);
// Порядок ВСЕГДА: apple, banana, cherry
for (String key : linkedMap.keySet()) {
    System.out.println(key); // apple, banana, cherry
}

// TreeMap — СОРТИРУЕТ по ключам
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("apple", 1);
treeMap.put("banana", 2);
treeMap.put("cherry", 3);
// Порядок ВСЕГДА: apple, banana, cherry (alphabetically!)
for (String key : treeMap.keySet()) {
    System.out.println(key); // apple, banana, cherry (sorted)
}

Как Работает LinkedHashMap Внутри?

LinkedHashMap использует двусвязный список поверх hash-таблицы:

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    // Двусвязный список для отслеживания порядка
    private transient Entry<K,V> head;  // Первый элемент
    private transient Entry<K,V> tail;  // Последний элемент
    
    // Каждый Node содержит:
    // - K key
    // - V value
    // - Node next (для следующего в порядке вставки)
    // - Node prev (для предыдущего в порядке вставки)
}

Визуализация:

HashMap hash table:  [bucket0] [bucket1] [bucket2] ... [bucketN]
                          ↓
                      "apple" → 1
                      
LinkedHashMap double-linked list:
(head) ← apple ↔ banana ↔ cherry → (tail)

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

1. Кэширование с Порядком Доступа (LRU Cache)

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // true = access-order (не insertion-order!)
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // Автоматически удаляем самый старый
    }
}

// Использование
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("user:1", "Alice");
cache.put("user:2", "Bob");
cache.put("user:3", "Charlie");

cache.get("user:1");  // Access user:1, переместили в конец
cache.put("user:4", "David");  // Полная — удалим самый старый (user:2)

// Порядок теперь: user:3, user:1, user:4

2. Сохранение Порядка в JSON Десериализации

// Проблема: обычный HashMap теряет порядок
Map<String, Object> data = new HashMap<>();
data.put("name", "Alice");
data.put("age", 30);
data.put("email", "alice@example.com");

String json = JsonUtils.toJson(data);
// JSON может быть: {"email": "...", "name": "...", "age": ...} (неправильный порядок!)

// Решение: использовать LinkedHashMap
Map<String, Object> data = new LinkedHashMap<>();
data.put("name", "Alice");
data.put("age", 30);
data.put("email", "alice@example.com");

String json = JsonUtils.toJson(data);
// JSON будет: {"name": "Alice", "age": 30, "email": "alice@example.com"} ✓

3. Обработка SQL Result Sets с Порядком Колонок

public Map<String, Object> resultSetToMap(ResultSet rs) throws SQLException {
    Map<String, Object> row = new LinkedHashMap<>();
    
    ResultSetMetaData metadata = rs.getMetaData();
    int columnCount = metadata.getColumnCount();
    
    for (int i = 1; i <= columnCount; i++) {
        String columnName = metadata.getColumnName(i);
        Object value = rs.getObject(i);
        row.put(columnName, value);
    }
    
    return row;  // Порядок колонок СОХРАНЕН!
}

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

           Time Complexity         Space Complexity
HashMap:   O(1) avg                O(n)
LinkedHashMap: O(1) avg            O(n) + двусвязный список (~2x память)
TreeMap:   O(log n)                O(n)

LinkedHashMap имеет незначительный overhead:

• ~10-15% медленнее чем HashMap на операциях
• ~1.5-2x больше памяти (за счет двусвязного списка)

Но это обычно не критично, и удобство часто стоит больше.

Difference: insertion-order vs access-order

// insertion-order (по умолчанию)
Map<String, Integer> map1 = new LinkedHashMap<>();
map1.put("a", 1);
map1.put("b", 2);
map1.put("a", 10);  // Переприсваиваем 'a'
// Порядок: a, b (a остается на первом месте, значение просто обновилось)

// access-order (третий параметр = true)
Map<String, Integer> map2 = new LinkedHashMap<>(16, 0.75f, true);
map2.put("a", 1);
map2.put("b", 2);
Integer val = map2.get("a");  // Обратились к 'a'
// Порядок: b, a (a переместился в конец как недавно использованный)

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

✅ Используй LinkedHashMap:

• Нужно сохранить порядок вставки элементов
• Реализуешь LRU/MRU cache
• Работаешь с JSON serialization
• Нужно predictable order для debugging
• Важен порядок параметров в SQL/API

❌ Используй HashMap:

• Порядок не важен
• Максимальная performance критична
• Используешь как простой key-value store

❌ Используй TreeMap:

• Нужна сортировка ключей
• Нужна range queries (subMap)
• Нужна natural ordering

Частые Ошибки

// ОШИБКА 1: забыли про LinkedHashMap
Map<String, Integer> map = new HashMap<>();  // Будет случайный порядок!

// ОШИБКА 2: LinkedHashMap с TreeMap (если нужна сортировка)
Map<String, Integer> map = new LinkedHashMap<>();  // Сохранит insertion-order, но не отсортирует!
// Правильно: используй TreeMap если нужна сортировка

// ОШИБКА 3: забыли про memory leak в LRU Cache
LinkedHashMap<String, byte[]> cache = new LinkedHashMap<String, byte[]>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 1000;  // Хорошо - предотвращаем утечку
    }
};
// Без removeEldestEntry кэш растет бесконечно!

Как Запомнить

• HashMap — "случайный" порядок
• LinkedHashMap — "linked" список сохраняет порядок
• TreeMap — "sorted" tree с сортировкой

Это базовое знание, которое часто проверяют на собеседованиях, и оно очень полезно на практике.