Как изменяется порядок элементов LinkedHashMap по последнему обращению к элементу

Ответ

LinkedHashMap и порядок обращения к элементам

LinkedHashMap — это реализация Map, которая сохраняет порядок элементов. По умолчанию она использует порядок вставки (insertion order), но может быть настроена для использования порядка доступа (access order).

Порядок по последнему обращению (Access Order)

Для настройки LinkedHashMap на использование access-order, нужно передать параметр accessOrder=true в конструктор:

import java.util.*;

public class LinkedHashMapAccessOrderExample {
    public static void main(String[] args) {
        // accessOrder=true означает порядок по последнему обращению
        LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                // Опционально: удалять элемент с наименьшей давностью использования
                return false; // не удаляем
            }
        };
        
        // Добавляем элементы
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);
        map.put("D", 4);
        
        System.out.println("После вставки: " + map.keySet()); // [A, B, C, D]
        
        // Обращаемся к элементам
        map.get("A"); // A переместится в конец (self-moving)
        System.out.println("После get(A): " + map.keySet()); // [B, C, D, A]
        
        map.get("C");
        System.out.println("После get(C): " + map.keySet()); // [B, D, A, C]
        
        map.put("E", 5); // Вставка также обновляет позицию
        System.out.println("После put(E): " + map.keySet()); // [B, D, A, C, E]
        
        // Итерируемся по map - порядок также обновляется
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        System.out.println("После итерации: " + map.keySet()); // [D, A, C, E, B]
    }
}

Как это работает внутри

LinkedHashMap использует двусвязный список (doubly-linked list) для сохранения порядка:

// Упрощённое представление внутренней структуры
public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private transient Entry<K, V> head;      // Начало списка
    private transient Entry<K, V> tail;      // Конец списка
    private final boolean accessOrder;       // true = access order, false = insertion order
    
    static class Entry<K, V> extends HashMap.Node<K, V> {
        Entry<K, V> before, after;            // Ссылки в двусвязном списке
    }
}

При обращении к элементу (access order):

1. Элемент перемещается из своей текущей позиции
2. Добавляется в конец списка (становится самым свежим)
3. Все остальные элементы сдвигаются влево

LRU Cache — практический пример

Акcess-order LinkedHashMap идеально подходит для реализации LRU (Least Recently Used) кеша:

import java.util.*;

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

public class LRUCacheExample {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");
        System.out.println("После добавления 1, 2, 3: " + cache.keySet()); // [1, 2, 3]
        
        cache.get(1); // Обращение к 1 - переместится в конец
        System.out.println("После get(1): " + cache.keySet()); // [2, 3, 1]
        
        cache.put(4, "Four"); // Добавляем 4-й элемент
        // 2 (самый давно использованный) будет удалён
        System.out.println("После put(4): " + cache.keySet()); // [3, 1, 4]
        
        cache.get(3);
        System.out.println("После get(3): " + cache.keySet()); // [1, 4, 3]
        
        cache.put(5, "Five"); // Добавляем 5-й элемент
        // 1 (самый давно использованный) будет удалён
        System.out.println("После put(5): " + cache.keySet()); // [4, 3, 5]
    }
}

Сравнение: Insertion Order vs Access Order

import java.util.*;

public class ComparisonExample {
    public static void main(String[] args) {
        // Insertion Order (accessOrder=false) - значение по умолчанию
        LinkedHashMap<String, Integer> insertionOrder = 
            new LinkedHashMap<String, Integer>(16, 0.75f, false);
        
        // Access Order (accessOrder=true)
        LinkedHashMap<String, Integer> accessOrder = 
            new LinkedHashMap<String, Integer>(16, 0.75f, true);
        
        // Заполняем обе map
        String[] keys = {"A", "B", "C"};
        for (String key : keys) {
            insertionOrder.put(key, 1);
            accessOrder.put(key, 1);
        }
        
        System.out.println("Insertion Order до get: " + insertionOrder.keySet()); // [A, B, C]
        System.out.println("Access Order до get: " + accessOrder.keySet());       // [A, B, C]
        
        // Обращаемся к "A"
        insertionOrder.get("A");
        accessOrder.get("A");
        
        System.out.println("Insertion Order после get(A): " + insertionOrder.keySet()); // [A, B, C] - не меняется!
        System.out.println("Access Order после get(A): " + accessOrder.keySet());       // [B, C, A] - A в конце
    }
}

Операции, обновляющие порядок (Access Order)

При accessOrder=true следующие операции перемещают элемент в конец:

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1);
map.put("B", 2);

// ✅ Обновляет порядок доступа
map.get("A");                    // Прямое обращение
map.getOrDefault("B", 0);        // getOrDefault
map.containsKey("A");            // containsKey в Java 8+
map.put("A", 10);                // put на существующий ключ

// ❌ НЕ обновляет порядок доступа
map.containsValue(100);           // Проверка по значению
map.size();                       // Получение размера
map.keySet();                     // Получение набора ключей

Важные характеристики

Потокобезопасный доступ

Map<String, Integer> syncMap = Collections.synchronizedMap(
    new LinkedHashMap<String, Integer>(16, 0.75f, true)
);

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

Выводы

1. LinkedHashMap с accessOrder=true перемещает элемент в конец при каждом обращении
2. Идеально подходит для реализации LRU кеша
3. Операции остаются O(1) как в обычной HashMap
4. Используй removeEldestEntry() для автоматического удаления старых элементов
5. Потокобезопасность требует дополнительной синхронизации