java全栈技术分享

主题

LinkedHashMap 源码解析 ​

简介 ​

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上维护了一条贯穿所有节点的双向链表，从而保证迭代顺序是可预测的。它与 HashMap 的关系可以概括为：HashMap 负责「查找」，LinkedHashMap 额外负责「维护顺序」。

  • 插入顺序（默认）：accessOrder = false 时，迭代顺序就是键值对的插入顺序。
  • 访问顺序：accessOrder = true 时，每次 get/put 已存在的 key 都会把该节点移到链表尾部，迭代顺序反映「最近最少使用（LRU）」的访问情况，因此非常适合实现 LRU 缓存。

LinkedHashMap 同样不是线程安全的；多线程环境下可以用 Collections.synchronizedMap 包装，或改用 ConcurrentHashMap。

注意：与 HashMap 一样，允许 null 键和 null 值；初始容量、负载因子等概念完全继承自 HashMap，对性能的影响也一致。

底层数据结构分析 ​

LinkedHashMap 的核心思路是：在 HashMap 的「数组 + 链表/红黑树」结构之外，再用 before/after 指针把所有节点串成一条双向链表。

java
// LinkedHashMap 的节点，继承自 HashMap.Node，多了 before / after 两个指针
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 里的 table、size、modCount 等字段外，LinkedHashMap 自己只多了三个关键字段：

java
// 双向链表的头节点（最久的节点）
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾节点（最新的节点）
transient LinkedHashMap.Entry<K,V> tail;

// 迭代顺序模式：false=插入顺序，true=访问顺序
final boolean accessOrder;

这样，同一个 Entry 同时存在于两处：

  1. HashMap 的桶（bucket）里，通过 next 指针解决哈希冲突（链表/红黑树）；
  2. LinkedHashMap 维护的双向链表里，通过 before/after 指针记录顺序。

因此 LinkedHashMap 的 get、遍历操作的时间复杂度与 HashMap 一致（理想 O(1)），只是每个节点多维护两个指针，内存占用略高。

源码分析 ​

构造方法 ​

LinkedHashMap 提供了多个构造方法，核心区别在于 accessOrder 的默认值。

java
// 默认构造：插入顺序
public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 唯一可以指定 accessOrder 的构造方法
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

// 从另一个 Map 构造，默认插入顺序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

节点接入：newNode 与 linkNodeLast ​

HashMap 在新增节点时调用 newNode()，LinkedHashMap 重写它，在创建节点的同时把节点链接到双向链表的尾部。

java
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;
}

// 红黑树节点同理
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

// 把节点 p 接到双向链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)          // 链表为空，head 也指向 p
        head = p;
    else {                     // 否则挂到原 tail 后面
        p.before = last;
        last.after = p;
    }
}

三个回调钩子（核心） ​

HashMap 在 putVal、remove、clear 等操作中会调用三个「空实现」的回调方法：afterNodeAccess、afterNodeInsertion、afterNodeRemoval。LinkedHashMap 正是通过重写这三个方法来维护双向链表的顺序。

1. afterNodeAccess：把节点移到链表尾部（访问顺序的关键）

java
void afterNodeAccess(Node<K,V> e) { // 把节点 e 移到链表尾部
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)              // e 原本是头节点
            head = a;
        else
            b.after = a;
        if (a != null)              // e 不是尾节点
            a.before = b;
        else                        // e 原本是尾节点
            last = b;
        if (last == null)           // 链表只剩 e 一个节点
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

当 accessOrder = true 时，get() 以及 put() 覆盖已存在 key 都会触发 afterNodeAccess，从而把刚访问的节点移动到尾部。配合 afterNodeInsertion 就能实现「淘汰最久未使用节点」的 LRU 语义。

2. afterNodeInsertion：插入后可能淘汰最老节点

java
void afterNodeInsertion(boolean evict) { // 可能移除最老的节点
    LinkedHashMap.Entry<K,V> first;
    // evict=true 且头节点存在，且 removeEldestEntry 返回 true 时淘汰
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

3. afterNodeRemoval：节点从 HashMap 移除时同步从链表摘除

java
void afterNodeRemoval(Node<K,V> e) { // 把节点 e 从双向链表中解除
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;       // 断开 e 自身的指针，方便 GC
    if (b == null)                   // e 是头节点
        head = a;
    else
        b.after = a;
    if (a == null)                   // e 是尾节点
        tail = b;
    else
        a.before = b;
}

get 方法（访问顺序的体现） ​

LinkedHashMap 重写了 get，在 HashMap.getNode 找到节点后，如果开启了访问顺序，会调用 afterNodeAccess 把节点移到尾部。

java
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;
}

// 类似地，getOrDefault 也会在访问顺序模式下触发 afterNodeAccess
@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

containsValue（按链表顺序遍历） ​

HashMap.containsValue 需要逐个桶扫描，而 LinkedHashMap 直接沿着双向链表从头到尾遍历即可，代码更简洁，且天然按维护的顺序进行。

java
public boolean containsValue(Object value) {
    // 沿双向链表 head -> after 顺序遍历，而非扫描 table
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

removeEldestEntry（实现 LRU 缓存的开关） ​

removeEldestEntry 默认永远返回 false，即不自动淘汰。子类（如 LRU 缓存）重写它即可在容量超限时淘汰最老节点。

java
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;   // 默认不淘汰；LRU 缓存可重写为 size() > maxSize
}

clear ​

清空时除了调用父类逻辑，还要把双向链表的头尾指针置空。

java
public void clear() {
    super.clear();
    head = tail = null;
}

与 HashMap 的关键区别 ​

维度HashMapLinkedHashMap
迭代顺序无序（受哈希影响）插入顺序 或 访问顺序
内存占用较少每个节点多两个指针，略大
get 性能O(1)O(1)，访问顺序下多一次链表移动
典型用途一般键值存储需要稳定迭代顺序、LRU 缓存

经典 Demo ​

java
import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // 1. 插入顺序（accessOrder 默认 false）
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        System.out.println(map); // {a=1, b=2, c=3}

        // 2. 访问顺序（accessOrder = true）
        LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
        lru.put("a", 1);
        lru.put("b", 2);
        lru.put("c", 3);
        lru.get("a"); // 访问 a，a 被移到队尾
        System.out.println(lru); // {b=2, c=3, a=1}

        // 3. 基于 LinkedHashMap 实现固定容量的 LRU 缓存
        LruCache<Integer, String> cache = new LruCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1);            // 访问 1，1 移到队尾
        cache.put(4, "four");    // 超过容量，淘汰最久未使用的 2
        System.out.println(cache); // {3=three, 1=one, 4=four}
    }

    // 固定容量的 LRU 缓存：重写 removeEldestEntry 即可
    static class LruCache<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        public LruCache(int maxSize) {
            super(maxSize, 0.75f, true); // accessOrder = true
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize; // 超过容量就淘汰最老节点
        }
    }
}