Что такое LinkedHashMap?

# LinkedHashMap: Полное описание

LinkedHashMap — это реализация интерфейса Map в Java, которая сохраняет порядок вставки элементов. Это гибрид между HashMap и LinkedList.

Базовая концепция

// HashMap - порядок НЕ гарантируется
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 1);
hashMap.put("banana", 2);
hashMap.put("cherry", 3);
// Выведет: {cherry=3, apple=1, banana=2} или в другом порядке
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);
}

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

LinkedHashMap расширяет HashMap и добавляет двусвязный список для отслеживания порядка:

// Упрощённая структура LinkedHashMap
public class LinkedHashMap<K, V> extends HashMap<K, V> {
    // ← наследует от HashMap
    
    // Добавляет ссылки на соседние элементы
    static class Entry<K, V> extends HashMap.Node<K, V> {
        Entry<K, V> before, after;  // ← для двусвязного списка
    }
    
    private transient Entry<K, V> head;  // ← начало списка
    private transient Entry<K, V> tail;  // ← конец списка
}

Визуально:

HashMap array (для быстрого поиска):
[bucket0] → hash collision chain
[bucket1] → Entry1 → Entry2
[bucket2] → Entry3
...

LinkedHashMap двусвязный список (для порядка):
head ↔ Entry1 ↔ Entry2 ↔ Entry3 ↔ tail

Два режима работы

1. Insertion-order (по умолчанию)

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("first", 1);
map.put("second", 2);
map.put("third", 3);
map.put("first", 10);  // ← Обновление НЕ меняет порядок

// Выведет в порядке вставки:
// first -> 10
// second -> 2
// third -> 3

2. Access-order (режим LRU)

LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(
    16,      // capacity
    0.75f,   // load factor
    true     // accessOrder = true (LRU mode)
) {
    // Перегрузим removeEldestEntry для LRU кеша
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 3;  // Максимум 3 элемента
    }
};

map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map.keySet());  // [a, b, c]

map.get("a");  // ← Доступ к "a" переместит его в конец
System.out.println(map.keySet());  // [b, c, a]

map.put("d", 4);  // ← Добавление новой записи
System.out.println(map.keySet());  // [c, a, d] ("b" удалён как самый старый)

Сложность операций

Ключевое отличие от HashMap: итерация по LinkedHashMap не требует scan всего array, итерируем по отсортированному списку.

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

Пример 1: Сохранение порядка параметров

// URL параметры нужно вывести в том же порядке
LinkedHashMap<String, String> params = new LinkedHashMap<>();
params.put("userId", "123");
params.put("action", "create");
params.put("timestamp", "2024-01-15");
params.put("signature", "abc123");

String query = params.entrySet().stream()
    .map(e -> e.getKey() + "=" + e.getValue())
    .collect(Collectors.joining("&"));
// userId=123&action=create&timestamp=2024-01-15&signature=abc123

Пример 2: LRU Cache (Least Recently Used)

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(16, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > maxSize;  // Удалить самый старый при переполнении
    }
}

// Использование
LRUCache<String, Integer> cache = new LRUCache<>(2);
cache.put("user1", 100);
cache.put("user2", 200);
cache.put("user3", 300);  // ← user1 удалится (самый старый)

Integer val = cache.get("user2");  // ← user2 теперь "свежий"
cache.put("user4", 400);  // ← user3 удалится (теперь самый старый)

System.out.println(cache.keySet());  // [user2, user4]

Пример 3: Запрет повторного добавления в разных местах

// Проверить, есть ли дубликаты с сохранением первого найденного
public static <T> List<T> removeDuplicates(List<T> list) {
    // LinkedHashMap сохраняет порядок, а ключи Map уникальны
    return new ArrayList<>(new LinkedHashMap<T, Boolean>(
        list.stream().collect(Collectors.toMap(
            Function.identity(),
            v -> true,
            (oldVal, newVal) -> oldVal,  // ← Сохраняем первый
            LinkedHashMap::new
        ))
    ).keySet());
}

List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 1, 4, 3, 5);
List<Integer> unique = removeDuplicates(numbers);
System.out.println(unique);  // [1, 2, 3, 4, 5] в порядке первого появления

Пример 4: Итерация с гарантированным порядком

public class ConfigParser {
    private LinkedHashMap<String, String> properties;
    
    public void parseConfig(String content) {
        properties = new LinkedHashMap<>();
        for (String line : content.split("\\n")) {
            String[] parts = line.split("=");
            if (parts.length == 2) {
                properties.put(parts[0].trim(), parts[1].trim());
            }
        }
    }
    
    // Сохраняет порядок конфига
    public String toConfigString() {
        StringBuilder sb = new StringBuilder();
        properties.forEach((k, v) -> {
            sb.append(k).append("=").append(v).append("\\n");
        });
        return sb.toString();
    }
}

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

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

1. Нужен порядок вставки

   // JSON парсер (сохранить порядок полей)
   LinkedHashMap<String, Object> jsonObject = new LinkedHashMap<>();
   

2. LRU Cache

   Map<String, User> userCache = new LinkedHashMap<>(16, 0.75f, true) {
       protected boolean removeEldestEntry(Map.Entry eldest) {
           return size() > 1000;  // Max 1000 пользователей
       }
   };
   

3. Сохранение порядка параметров

   LinkedHashMap<String, String> queryParams = new LinkedHashMap<>();
   

4. Конфигурационные файлы

   LinkedHashMap<String, String> config = new LinkedHashMap<>();
   // Гарантирует сохранение порядка при записи обратно
   

❌ Не используй LinkedHashMap:

1. Когда порядок не важен → Используй HashMap (быстрее, меньше памяти)

2. Когда нужна сортировка → Используй TreeMap (сортирует по ключу)

3. Высоконагруженные системы → LinkedHashMap медленнее HashMap на 10-20%

Сравнение HashMap, LinkedHashMap, TreeMap

Потокобезопасность

// LinkedHashMap НЕ потокобезопасен
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

// Для многопоточности:
Map<String, Integer> syncMap = Collections.synchronizedMap(
    new LinkedHashMap<>()
);

// Или использовать ConcurrentHashMap (без гарантии порядка)
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

Резюме

LinkedHashMap:

• ✅ Сохраняет порядок вставки (по умолчанию)
• ✅ Может работать в режиме LRU (по порядку доступа)
• ✅ O(1) для get/put (как HashMap)
• ✅ Идеален для кешей и конфигов
• ❌ Медленнее HashMap (двусвязный список добавляет overhead)
• ❌ Больше памяти
• ❌ Не потокобезопасен

Практическое применение: LRU Cache, JSON parsing с сохранением порядка, URL параметры, конфигурационные файлы.