LinkedHashMap源码剖析

类定义与继承结构

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

它继承自 HashMap，但加入了顺序维护能力，通过内部维护一个双向链表实现插入顺序或访问顺序。

核心数据结构

LinkedHashMap 除了继承 HashMap 的数组 + 链表/红黑树结构外，新增了前驱后继指针：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

每个 Entry 不仅记录 key、value、hash、next，还额外维护：

• before: 指向前一个 Entry；
• after: 指向后一个 Entry。

整个 LinkedHashMap 就形成了一个双向链表结构。

顺序控制关键：accessOrder 标志

private final boolean accessOrder;

• false（默认）：按插入顺序记录；
• true：按访问顺序记录（如 get() 会调整位置）。

这个标志由构造函数指定：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

插入逻辑：维护链表结构

LinkedHashMap 重写了 newNode() 和 afterNodeInsertion() 方法来维护链表顺序：

插入新元素

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

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

插入元素时会将其追加到双向链表的末尾，形成插入顺序的维护。

访问逻辑：按访问顺序调整（可选）

void afterNodeAccess(Node<K,V> e) {
    if (accessOrder) {
        LinkedHashMap.Entry<K,V> last = tail;
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e;
        if (last != p) {
            // 移除旧位置
            LinkedHashMap.Entry<K,V> b = p.before;
            LinkedHashMap.Entry<K,V> a = p.after;
            if (b != null)
                b.after = a;
            else
                head = a;
            if (a != null)
                a.before = b;
            else
                tail = b;
            // 插入末尾
            p.after = null;
            p.before = last;
            if (last != null)
                last.after = p;
            tail = p;
        }
    }
}

如果 accessOrder 为 true，则每次访问（如 get）都将该节点移至末尾，实现 LRU（最近最少使用）策略的访问顺序维护。

删除逻辑：保持链表一致性

重写了 afterNodeRemoval() 方法：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e;
    LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

删除 Entry 时，同时断开它在双向链表中的连接。

自动删除机制：LRU 缓存的关键

重写 removeEldestEntry() 可实现自动删除最旧元素（例如用于实现 LRU 缓存）：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默认返回 false，不删除
}

如果你继承 LinkedHashMap 并重写该方法：

@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > MAX_SIZE;
}

就可以自动删除最旧的元素了（通常是 head 指向的 Entry）。

遍历顺序与迭代器

LinkedHashMap 保证迭代时顺序与双向链表顺序一致（插入顺序或访问顺序）：

for (Map.Entry<K, V> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

不同于 HashMap 无序遍历，LinkedHashMap 顺序是稳定的。

总结

⬅️ LinkedHashMap 🏠 00-Java ➡️ TreeMap