---
url: https://www.chenlj.top/md/java-base/collections/LinkedHashMap.md
---
# 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 的关键区别

| 维度 | HashMap | LinkedHashMap |
| --- | --- | --- |
| 迭代顺序 | 无序（受哈希影响） | 插入顺序 或 访问顺序 |
| 内存占用 | 较少 | 每个节点多两个指针，略大 |
| 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; // 超过容量就淘汰最老节点
        }
    }
}
```