前言

在 Java 集合框架中，LinkedHashMap 可能是最容易被轻视，但设计得极其巧妙的一个类。它是 HashMap 的直接子类，源码量非常少，因为它直接复用了 HashMap 的 90% 以上的代码。

它唯一的秘密武器就是：在数组+链表/红黑树的基础上，额外增加了一根穿过所有节点的“红线”——双向链表。

---

一、 核心结构：双向链表的节点

首先看它的内部节点类 Entry，它继承了 HashMap.Node：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 这一对指针是关键！
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

• HashMap.Node：负责哈希表中的连接（为了查询快）。

• before 和 after：负责维护节点在集合中的逻辑顺序（为了遍历有序）。

---

二、 两种排序模式：插入顺序 vs 访问顺序

LinkedHashMap 有一个神奇的参数 accessOrder，在构造函数中可以设置：

1. 插入顺序 (accessOrder = false)：默认模式。遍历顺序就是你 put 元素的顺序。

2. 访问顺序 (accessOrder = true)：LRU（最近最少使用）算法的基石。当你 get 或 put 一个元素后，该元素会自动移到链表的末尾。

---

三、 源码级解析：它是如何“插桩”的？

由于 LinkedHashMap 继承了 HashMap，它并没有重写 put 方法，而是重写了 HashMap 预留的三个“钩子方法”（Hook Methods）：

1. 节点创建时的挂载

当 HashMap 创建新节点时，会调用 newNode。LinkedHashMap 重写了它：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p); // 核心：每创建一个新节点，顺便把它挂到双向链表的末尾
    return p;
}

2. 访问后的位置移动

如果你开启了 accessOrder = true，当你调用 get 方法时：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e); // 钩子方法：将当前节点移到双向链表最后
    return e.value;
}

afterNodeAccess 的逻辑非常简单：从双向链表的当前位置“抠出来”，重新插到 tail 后面。

---

四、 实战必杀技：手写一个 LRU Cache

这是大厂面试的高频算法题。利用 LinkedHashMap，你只需要几行代码就能实现一个工业级的 LRU 缓存。

核心在于重写 removeEldestEntry 方法：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    public LRUCache(int capacity) {
    // true 表示开启访问顺序
    super(capacity, 0.75f, true);
    this.capacity = capacity;
  }
​
  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    // 当 Map 大小超过阈值时，自动删除最老（最近最少使用）的元素
    return size() > capacity;
  }
}
  

原理：HashMap 在 put 结束后会调用 afterNodeInsertion，而该方法内部会根据 removeEldestEntry 的返回值决定是否移除链表头部的节点（最老的节点）。

---

五、 性能开销：多出来的“红线”代价大吗？

• 时间复杂度：依然是 O(1)。虽然多了指针维护，但这些操作都是常数级的。

• 遍历效率：高于 HashMap。

  • HashMap 遍历时需要扫描整个数组桶（包括空桶）。

  • LinkedHashMap 遍历时直接走双向链表，只扫描有数据的节点。

• 空间复杂度：由于每个节点多了两个指针引用，内存消耗会比 HashMap 略大。

---

六、 总结：什么时候该想起它？

作为资深开发，你应该在以下场景优先考虑 LinkedHashMap：

1. 需要保持顺序：比如做 JSON 序列化输出，希望字段顺序和存入顺序一致。

2. 缓存失效策略：实现简单的 LRU 缓存。

3. 替代 TreeMap：如果你只需要插入顺序而不需要按 Key 的自然大小排序，LinkedHashMap 的性能远优于 TreeMap（O(1) vs O(logn)）。

---

结语： LinkedHashMap 是 Java 继承与多态设计的一个范本。它告诉我们：通过合理的“插桩”和扩展，可以在不破坏原有高性能逻辑的基础上，优雅地增加新功能。