LinkedHashMap 和前移编码

前移编码：最老的元素在最前面。

当 LinkedHashMap 设置为访问顺序模式时，被访问的元素会从当前位置移动到双向链表的[尾部]，成为"最新"的元素。
移动节点到尾部 核心方法afterNodeAccess(Node<K,V> e)。
前移机制使得 LinkedHashMap 成为实现 LRU 缓存和其他需要访问顺序跟踪功能的理想选择。

LinkedHashMap 是 Java 集合框架中的一个重要类，它继承自 HashMap，同时维护了一个双向链表来保持元素的插入顺序或访问顺序。
LinkedHashMap 在 HashMap 的基础上增加了双向链表：

// 默认构造函数（初始容量16，负载因子0.75）
LinkedHashMap<String, Integer> map1 = new LinkedHashMap<>();

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

// 使用示例
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("1", "One");
cache.put("2", "Two");
cache.put("3", "Three");
cache.get("1");    // 访问 "1"，使其成为最近使用的
cache.put("4", "Four"); // 会自动移除最久未使用的 "2"

LinkedHashMap 是一个功能强大的 Map 实现，它在 HashMap 的基础上提供了可预测的迭代顺序。通过灵活使用其排序模式和 removeEldestEntry 方法，可以轻松实现各种高级功能，特别是 LRU 缓存场景。

性能特点

时间复杂度：
添加、删除、查找：O(1)（平均情况）
迭代：O(n)（比 HashMap 稍快，因为直接遍历链表）
空间复杂度：比 HashMap 略高（需要维护双向链表）

与 HashMap 的比较

特性 HashMap LinkedHashMap
迭代顺序 不保证 保证插入顺序或访问顺序
性能 稍快 稍慢（需要维护链表）
内存使用 较少 较多
线程安全 否 否

// 基本使用
LinkedHashMap<String, Integer> scores = new LinkedHashMap<>();
scores.put("Alice", 90);
scores.put("Bob", 85);
scores.put("Charlie", 95);

// 保持插入顺序迭代
scores.forEach((name, score) -> 
    System.out.println(name + ": " + score));

// 访问顺序示例
LinkedHashMap<String, Integer> accessOrderMap = 
    new LinkedHashMap<>(16, 0.75f, true);
accessOrderMap.put("A", 1);
accessOrderMap.put("B", 2);
accessOrderMap.put("C", 3);

accessOrderMap.get("A"); // 访问 A，使其移动到末尾
// 迭代顺序：B -> C -> A

LinkedHashMap 自动删除机制详解

删除的是队首（最老）的元素

当启用自动删除功能时，LinkedHashMap 删除的是双向链表的队首（head）元素，也就是最久未使用或最早插入的元素。
新访问或插入的元素移动到 tail（成为最新）

head (最老) ↔ Entry1 ↔ Entry2 ↔ ... ↔ tail (最新)

// 在HashMap的putVal方法最后会调用
afterNodeInsertion(evict);

// LinkedHashMap的实现：这就是为什么 LinkedHashMap 能够完美实现 LRU 缓存机制的原因。
void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    // 获取head（最老的元素）并进行判断
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true); // 删除head
    }
}