---
title: "04-LinkedHashMap源码剖析"
created: 2025-12-02
tags:
  - Java
---
# LinkedHashMap源码剖析

> [!note] 定位说明
> Map 系列第 4 篇深读篇：看 HashMap 的钩子方法（afterNodeAccess/afterNodeInsertion）如何被子类利用——模板方法模式的教科书案例。

### 类定义与继承结构

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

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

### 核心数据结构

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

```java
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 标志

```java
private final boolean accessOrder;
```

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

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

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

### 插入逻辑：维护链表结构

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

#### 插入新元素

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

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

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

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

```java
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()` 方法：

```java
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 缓存）：

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

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

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

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

### 遍历顺序与迭代器

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

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

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

### 总结

| 特性 | HashMap | LinkedHashMap |
| --- | --- | --- |
| 顺序 | 无序 | 插入顺序 / 访问顺序 |
| 底层结构 | 哈希表 | 哈希表 + 双向链表 |
| 迭代顺序 | 不稳定 | 稳定（按链表顺序） |
| 额外空间开销 | 少 | 每个节点多两个指针（before/after） |
| 应用 | 通用键值映射 | 有顺序需求，或 LRU 缓存 |
---
⬅️ [[03-LinkedHashMap|LinkedHashMap]] 🏠 [[00-Java|00-Java]] ➡️ [[05-TreeMap|TreeMap]]