JDK21 中的 LinkedHashMap

封面来源：碧蓝航线 雪境迷踪 活动 CG

0. 前言

这篇文章最迟应该在四月底发出，但因为自己半吊子的电脑知识，在 4 月 24 日下午对电脑使用了 BIOS 的云端还原，这不仅导致系统盘被还原，另一块存放资料的硬盘也被清空，其中就包括即将截稿的本文。

如果损失仅此而已倒也还好，但现实情况往往比这更糟，一些未备份的资料也在本次误操作中被清空殆尽。

从毕业后的那一年开始，我逐渐意识到时间的残忍，七千个日夜并未在我脑海中留下过多的印记，只有那些刻骨铭心、终身难忘的回忆会在未来某天遇到类似的场景后浮现。为了日后能够更好地拾起这些碎片，我开始使用文字记录生活。保存这些记忆的文件并没有使用版本控制，也没有使用云端同步，仅仅是手动备份到 U 盘里。

如果能够定期手动备份也还好，但这在去年购置新电脑后便停止了，一方面对新电脑的信任，另一方面也是发现这样的备份过于麻烦，只是没想到一年后会出现这样的事。

再次翻看备份时，最后的日期停留在去年的 5 月 18 日，那一瞬间，时间管理局将我的时间线从那天掐断，再把它接到现在的时间点。

言归正传，本文与 双端队列 ArrarDeque 一文类似，将介绍 JDK21 中一种内置的数据结构 —— LinkedHashMap。

1. LinkedHashMap 概述

LinkedHashMap 在 HashMap 的基础上进行了拓展，这在其类定义上也能看出：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements SequencedMap<K,V>
{
    // --snip--
}

它继承了 HashMap，也就是说具备 HashMap 的全部能力，除此之外还实现了 SequencedMap 接口。

JDK21 对集合进行了补强，新增了“有序集合”，对于 Map 来说则是新增了 SequencedMap 接口，它表明 Map 内的元素是有顺序的，并提供了对集合中首个、末位元素的操作方式，这在其内部的方法定义中也能看出：

public interface SequencedMap<K, V> extends Map<K, V> {
    
    SequencedMap<K, V> reversed();
    
    default Map.Entry<K,V> firstEntry() {
        // --snip--
    }

    default Map.Entry<K,V> lastEntry() {
    	// --snip--
	}

	default Map.Entry<K,V> pollFirstEntry() {
        // --snip--
    }
    
    default Map.Entry<K,V> pollLastEntry() {
        // --snip--
    }
    
    default V putFirst(K k, V v) {
        // --snip--
    }
    
    default V putLast(K k, V v) {
        // --snip--
    }
    
    default SequencedSet<K> sequencedKeySet() {
        // --snip--
    }
    
    default SequencedCollection<V> sequencedValues() {
        // --snip--
    }
    
    default SequencedSet<Map.Entry<K, V>> sequencedEntrySet() {
        // --snip--
    }
}

除此之外，JDK21 还引入了 SequencedCollection 接口，这个接口和 SequencedMap 类似，只不过适用于集合。

众所周知，LinkedHashMap 在内部维护了一条双向链表，链表中元素的顺序即为调用 put() 方法时插入元素的顺序，但这并不是 LinkedHashMap 的全部，如果需要实现一个 LRU 缓存，就像 146. LRU 缓存 一样，此时借助 LinkedHashMap 就能轻松解决。

2. 成员变量与常量

2.1 成员变量

LinkedHashMap 中的成员变量，一共有 4 个，分别是：

1. LinkedHashMap.Entry<K,V> head：双向链表的头指针（最年长的）
2. LinkedHashMap.Entry<K,V> tail：双向链表的尾指针（最年轻的）
3. boolean accessOrder：LinkHashMap 的迭代顺序方式，true 表示通过访问顺序，false 表示通过插入顺序
4. int putMode = PUT_NORM：元素的插入模式，它一共有三个可选值，这会在后续介绍常量时讲到

2.2 常量

LinkedHashMap 中有 3 个重要的常量，它们是成员变量 putMode 的可选值，定义了不同的插入模式：

1. int PUT_NORM = 0：标准的插入模式，将新添加的元素放在链表最后面
2. int PUT_FIRST = 1：将新添加的元素放在链表的最前面
3. int PUT_LAST = 2：将新添加的元素放在链表最后面

PUT_NORM 和 PUT_LAST 的功能类似，但它们却表示不同的含义，当使用 PUT_LAST 时，明确表示希望将新添加的元素放在链表最后面，而不是依赖默认行为，并且也不能保证在未来的实现中使得 PUT_NORM 表示的含义发生变化（虽然这不太可能 😅），设计成两个变量为了代码的可读性和灵活性。

这三个值并不存在于低版本的 JDK 中，JDK21 引入了 SequencedMap 接口，这三个用于实现该接口中的相关功能。

2.3 Entry 静态嵌套类

介绍成员变量时，引入了 LinkedHashMap.Entry，它是 LinkedHashMap 的一个静态嵌套类：

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

Entry 是 HashMap 里静态嵌套类 Node 的子类，在 Node 的基础上新增成员变量 before 和 after，能够更方便地表示双向链表里每个节点的前一个、后一个节点。

3. 构造函数

LinkedHashMap 提供了五种不同的构造函数，其中三种是：

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

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

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

父类 HashMap 也提供了类似的构造函数，因此不再赘述。

剩下两种构造函数允许通过以下方式来构造当前的 LinkedHashMap：

• 通过一个现有的 Map
• 构造具有指定的 accessOrder 值的 LinkedHashMap

3.1 通过现有的 Map 构造

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

构造出的 LinkedHashMap 的 accessOrder 值为 false，也就是在遍历当前 Map 时将按照元素的插入顺序。

重点是调用的 putMapEntries() 方法，该方法是父类 HashMap 中的：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // --snip--
}

方法被 final 修饰，不能被子类重写。

忽略方法体，单从参数与方法名称可知，putMapEntries() 方法是用于将传入的 Map 对象添加到当前 Map 实例中。

那第二个 boolean 类型的 evict 参数有什么用呢？

evict 意为驱逐、逐出，比如需要移除缓存中的某个元素时，就可以使用该词，比如 evictCache。此处的含义也大致类似，具体作用卖个关子，但根据 putMapEntries() 的方法注释可知：

• 调用该方法来构造 Map 时，evict 的值应该为 false，否则为 true。evict 的值会被传递到 afterNodeInsertion() 方法。

注释并未告诉我们 evict 的作用是什么，但似乎与 afterNodeInsertion() 方法有关。

暂且按下不表，最终答案会在后续讲解 put 的实现时揭晓。

3.2 指定 accessOrder 值

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

显式指定构造的 LinkedHashMap 的 accessOrder 值，该值指定了遍历该 Map 的方式，是通过访问顺序，还是通过插入顺序，其具体实现也将在后文揭晓。

4. 插入节点

LinkedHashMap 并未重写父类 HashMap 的 put() 方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

底层最终调用的是 putVal() 方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // --snip--
}               

putVal() 方法被 final 修饰，不能够被子类重写。简单介绍下它各个参数的含义：

• hash：插入 key 的哈希值
• key：插入的 key
• value：插入的 value
• onlyIfAbsent：是否只在 key 不存在时才插入 value
• evict：传入到 afterNodeInsertion()方法中使用

LinkedHashMap既没有重写 put()方法，putVal()方法又被 final 修饰，无法被重写，那 LinkedHashMap 是怎么实现自己的特殊逻辑呢？比如遍历元素时会按照插入顺序进行遍历。

putVal() 方法内部调用了许多钩子方法，这些钩子方法能够被子类重写，使得子类能够实现自身的独有逻辑（使用了模板方法设计模式）：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // --snip--
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 添加的 key 对应的索引不存在时
        tab[i] = newNode(hash, key, value, null);
    else {
        // --snip--
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 解决哈希冲突后调用
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 节点插入后调用
    afterNodeInsertion(evict);
    return null;
}

在上面截取的 putVal() 方法实现中能够看到，共调用了 3 个方法：

1. newNode()
2. afterNodeAccess()
3. afterNodeInsertion()

4.1 newNode

通过插入的 key 计算出的索引位置对应的值是 null 时，就会调用 newNode() 方法来创建一个新节点，并将新节点放在这个索引位置。

HashMap 中的实现很简单，创建出 Node 实例直接就返回了：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

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);
    linkNodeAtEnd(p);
    return p;
}

通常是创建出 Entry 实例然后返回，只不过中间调用了特有的 linkNodeAtEnd() 方法。该方法接收一个 Entry 类型的参数，从其名称可以大胆推断出此方法是用于将传入的 Entry 链接到 LinkedHashMap 内部维护的双向链表中：

// link at the end of list
private void linkNodeAtEnd(LinkedHashMap.Entry<K,V> p) {
    if (putMode == PUT_FIRST) {
        LinkedHashMap.Entry<K,V> first = head;
        head = p;
        if (first == null)
            tail = p;
        else {
            p.after = first;
            first.before = p;
        }
    } else {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
}

linkNodeAtEnd() 方法会根据不同的 putMode 执行不同的链接方式，以 putMode == PUT_FIRST 为例，即将传入的 p 链接到链表的头部：

1. 首先获取双向链表的头节点，并备份为 first：

   LinkedHashMap.Entry<K,V> first = head;
   head = p;

2. 判断头结点是否为 null，也就是判断当前链表中是否不存在节点；

3. 如果头结点为 null，相当于插入的节点 p 将会成为链表里唯一的节点，此时将双向链表的尾指针 tail 指向 p：

   tail = p;

4. 如果头结点不为 null，即原链表中至少存在一个元素，此时将 p 的 after 指针指向头结点，将头结点的 before 指针指向 p，使得 p 成为双向链表中新的头结点：

   p.after = first;
   first.before = p;

通过前文对 LinkedHashMap 中常量的分析，putMode 有 3 个可选值，除了 PUT_FIRST 外，还可以是 PUT_NORM 和 PUT_LAST。当 putMode 的值是这两种情况时，新添加的节点 p 会被链接到双向链表的尾部。

4.2 afterNodeAccess

向 Map 中添加元素，key 的哈希值产生了哈希冲突，并且还能够找到现有 key 的情况下时，会调用 afterNodeAccess() 方法。

简单分析下 putVal() 中的逻辑：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // --snip--
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 不存在哈希冲突，直接 newNode
        tab[i] = newNode(hash, key, value, null);
    else {
        // 出现哈希冲突
        Node<K,V> e; K k;
        // 命中桶中的第一个节点（与第一个节点 key 的哈希值相同，equals 也相同）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 在红黑树中找到相同的 key
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 在链表中找到相同的 key
            for (int binCount = 0; ; ++binCount) {
                // 在链表的最后一个节点
                if ((e = p.next) == null) {
                    // newNode 加到链表尾
                    p.next = newNode(hash, key, value, null);
                    // 判断是否需要树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 在链表尾添加节点后就跳出循环
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 找到相同的 key，跳出循环
                    break;
                p = e;
            }
        }
        // 产生哈希冲突时，找到现有的 key
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 执行目标方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // --snip--
    return null;
}

这里还有个小问题：产生哈希冲突后，会尝试在链表或者红黑树中找是否存在现有 key，如果不存在，应该要 newNode()，并维护 LinkedHashMap 中的双向链表。尝试在链表中查找时，如果不存在，显式调用了 newNode() 方法，但是尝试在红黑树中查找时，仅仅是调用了 putTreeVal() 方法，这个方法内部会调用 newNode() 方法吗？

稍加思索可知，内部实现肯定会调用 newNode() 方法，不然怎么维护那个双向链表呢？

这里就不贴 putTreeVal() 的代码实现了，但其内部确实没有调用 newNode() 方法，但调用了 newTreeNode()，它与 newNode() 大同小异，LinkedHashMap 内部也重写了它：

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
    linkNodeAtEnd(p);
    return p;
}

只能说是相当熟悉了。😂

简单总结下 put 流程：

1. 如果没产生哈希冲突，new 个 node；
2. 如果产生哈希冲突：
   • 尝试找现有 key，如果找到，判断是否需要执行 value 的覆盖，最后返回旧的 value；
   • 如果没找到现有 key，那么可能会将节点加到链表或者红黑树中，但无论是哪一种，都会调用 newNode() 或类似的方法，维护 LinkedHashMap 中的双向链表。

回归正题，afterNodeAccess() 在 HashMap 中是一个空实现，LinkedHashMap 对其进行了重写，这是因为 HashMap 不会因为访问了节点而执行特殊逻辑，但 LinkedHashMap 需要执行特殊逻辑。

LinkedHashMap 会 根据不同的 putMode 将当前双向链表中的节点移动到链表尾部或者链表首部。

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    LinkedHashMap.Entry<K,V> first;
    if ((putMode == PUT_LAST || (putMode == PUT_NORM && accessOrder)) && (last = tail) != e) {
        // --snip--
    } else if (putMode == PUT_FIRST && (first = head) != e) {
        // --snip--
    }
}

JDK21 中重写的 afterNodeAccess() 方法实现有点长，接下来将逐一分析每一个 if 及其内部实现的含义。

首先是第一个 if，其中有三个判断：

1. putMode == PUT_LAST：当前 putMode 是将元素插入到链表末尾
2. putMode == PUT_NORM && accessOrder：当前 putMode 是标准实现，但是当前 LinkedHashMap 将会通过访问顺序遍历（即 accessOrder == true），此时应该将新插入的元素放到链表末尾
3. (last = tail) != e：链表末尾的元素不是新添加的元素

第一个 if 的内部实现用于将链表中已存在的节点移动到链表尾部，因此 (last = tail) != e 的判断也很好理解了，如果末尾的元素已经是新添加的元素，自然不再需要移动节点。

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    LinkedHashMap.Entry<K,V> first;
    if ((putMode == PUT_LAST || (putMode == PUT_NORM && accessOrder)) && (last = tail) != e) {
        // move node to last
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    } else if (putMode == PUT_FIRST && (first = head) != e) {
        // --snip--
    }
}

逐一分析内部实现：

• 将 Node 类型的 e 对象强转成 Entry 类型的 p，备份下 p 的 before 和 after 指针，便于后续修改

  LinkedHashMap.Entry<K,V> p =
      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

• 令 p 的 after 为 null，因为移到末尾后，末尾不再有其他节点

  p.after = null;

• 链接 p 的前一个节点与后一个节点：判断原先 p 的前一个节点是否是 null（相当于原先 p 是链表的第一个节点），如果是 null，将双向链表的头指针指向原先 p 的后一个节点；如果不是 null，将原先 p 的前一个节点的 after 指针指向原先 p 的后一个节点

  if (b == null)
      head = a;
  else
      b.after = a;

• 链接 p 的后一个节点与前一个节点：判断原先 p 的后一个节点是否是 null（相当于原先 p 是链表的最后一个节点），如果不是 null，将原先 p 的后一个节点的 before 指针指向原先 p 的前一个节点；如果是 null，将双向链表的尾指针指向原先 p 的前一个节点

  if (a != null)
      a.before = b;
  else
      last = b;

• 经过前面的步骤，节点 p 已经从链表中摘了出来，并把其前驱节点和后继节点关联了起来，接下来需要将节点 p 放到链表的末尾。将 p 的 before 指针指向原先的尾节点（即 last），原先尾节点的 after 指针指向现在的 p

  if (last == null)
      head = p;
  else {
      p.before = last;
      last.after = p;
  }

  前面描述的逻辑是 else 块中的内容，实际运行过程中一般不会执行 if 块中的内容，即 last == null 的判断条件通常是不会满足的。

• 现在 p 也被添加到链表末尾了，最后让 tail 指针指向新的尾结点 p，modCount 自增一

  tail = p;
  // 修改计数加一
  ++modCount;

  到此，节点 p 已经从链表中被移动到了链表尾，afterNodeAccess() 方法的另一半实现也类似，只不过是将节点 p 从链表中移动到链表首，就不再赘述了。

前面提到在实际运行过程中一般不会满足 last == null，这是为什么？

last 的来源有两处。

第一处是最外层的判断中，将尾指针赋值给 last：

if ((putMode == PUT_LAST || (putMode == PUT_NORM && accessOrder)) && (last = tail) != e) {
    // --snip--
}

如果 last == null 的条件成立，那么 tail == null 也成立，此时链表中应该不含任何节点。

但 afterNodeAccess() 方法能够被执行，是表明在 LinkedHashMap 中找到了现有 key，链表中至少含有一个节点，与假设矛盾，因此第一处来源不能使 last == null 的条件成立。

第二处是在 if 块中，当 a == null 时，将 b 赋值给 last：

if (a != null)
    a.before = b;
else
    last = b;

a 表示节点 p 的后继节点，当 a == null 时，表示 p 没有后继节点，即 p 是链表中最后一个节点。

如果 last == null 成立，那么 b == null 成立，b 表示节点 p 的前驱节点，即 p 是链表中第一个节点。

综上可得，在这种情况下，p 既是链表中第一个节点，也是链表中最后一个节点，那么 p 是链表中唯一的节点。

如果 p 是链表中唯一的节点，在最外层判断 (last = tail) != e 将不成立，无法继续执行 if 块中的代码，与假设矛盾，因此第二处的来源也不能使 last == null 的条件成立。

无论哪一种来源，都不能使 last == null 的条件成立，因此实际运行过程中一般不会触发，这个判断条件更像是为了处理极端情况或者防御性编程而添加的。

4.3 afterNodeInsertion

在 putVal() 方法最后会执行 afterNodeInsertion() 方法，该方法接收 boolean 类型的参数，其参数值就是调用 putVal() 方法时传入的 evict。

HashMap 内部的 afterNodeInsertion() 方法是一个空实现，LinkedHashMap 对其进行进行了重写：

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

实现比较简单，满足 evict == true，链表中有节点，并且 removeEldestEntry() 方法也返回 true，那么会获取链表中的第一个节点，然后移除它。

根据注释 possibly remove eldest 的含义，这将移除“最老的”节点。

重点来到 removeEldestEntry() 方法：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

该方法被 protected 修饰，允许被子类重写。接收 Entry 类型的参数，即 LinkedHashMap 内部维护的双向链表的“最老的”节点。当这个方法返回 true 时，就会删除“最老的”节点。

实现 LRU 缓存

利用这个方法能够很容易实现 LRU 缓存，比如初始化 LRU 缓存对象时要求执行一个 capacity 的值，该值作为缓存的最大容量，如果插入操作导致缓存对象数量超过了 capacity ，则应该 逐出 最久未使用的对象。

通过继承 LinekdHashMap 并重写 removeEldestEntry() 方法，这样的 LRU 缓存非常容易实现，假设缓存的 key 和 value 类型都是 Integer 类型：

public class LRUCache extends LinkedHashMap<Integer, Integer> {

    @Serial
    private static final long serialVersionUID = -8424577645842772711L;

    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

直接秒了，简单而优雅。😎

4.4 JDK21 的补强

新增的 SequencedMap 接口也为 LinkedHashMap 带来了新特性，其中与元素插入相关的方法有 putFirst() 和 putLast()，它们在 LinkedHashMap 中的实现依赖于 put() 方法，因此这里简单贴下代码实现，底层逻辑在前文中已经介绍过了：

public V putFirst(K k, V v) {
    try {
        putMode = PUT_FIRST;
        return this.put(k, v);
    } finally {
        putMode = PUT_NORM;
    }
}

public V putLast(K k, V v) {
    try {
        putMode = PUT_LAST;
        return this.put(k, v);
    } finally {
        putMode = PUT_NORM;
    }
}

4.5 节点插入总结

到此，LinkedHashMap 的插入操作就分析完了，一张图概括一下：

flowchart TD
	a([开始])
	b{是否产生哈希冲突}
	c["newNode()"]
	d{是否存在现有key}
	e["newNode()"]
	f["执行 afterNodeAccess()，并返回旧值"]
	g["afterNodeInsertion()"]
	z([结束])
	a-->b
	b-->|否|c-->g
	b-->|是|d
	d-->|否|e-->g
	d-->|是|f-->z
	g-->z

5. 其他常用 API

Map 内常用的 API 不外乎就以下几种：

public interface Map<K, V>{
    int size();
    boolean isEmpty();
    V put(K key, V value);
    V get(K key);
    V remove(K key);
    void clear();
    boolean containsKey(K key);
    boolean containsValue(V value);
    
    // --snip--
}

除此之外还有一些与 Map 视图相关的 API，比如 keySet()、values() 等等，这将在后文讲解遍历 LinkedHashMap 时介绍。

前一节重点介绍了 LinkedHashMap 中 put() 方法的实现，在上述列出的 API 中，size() 与 isEmpty() 方法沿用了父类 HashMap 的实现，此处不再赘述，本节将讲解剩下数个 API 的实现。

5.1 get

因为 LinkedHashMap 需要外维护一条双向链表，与 HashMap 相比，其 put() 方法的实现要稍微复杂点，但大多数也都是建立在 HashMap 的基础上，因此前文使用了大量篇幅进行讲解。

与 put() 的实现相比，get() 的实现就“稍显逊色”了，后者基本完全沿用了 HashMap 的实现。

// LinkedHashMap 的实现
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

// HashMap 的实现
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(key)) == null ? null : e.value;
}

可以看到，与 HashMap 的实现相比，LinkedHashMap 的实现增加了对 accessOrder 成员变量的判断，当其值为 true 时，会额外执行 afterNodeAccess() 方法。该方法在前文中已经介绍过，它会根据不同的 putMode 将当前双向链表中的节点移动到链表尾部或者链表首部。

除非显式设置了 putMode 的值，它的值始终是 PUT_NORM，而且就算显式设置了，当主要逻辑执行外之后，也会讲它的值再修改回 PUT_NORM，这在 putFirst() 和 putLast() 的实现中可见一斑。

因此在调用 get() 方法时，putMode 的值总是 PUT_NORM，根据前文的分析，满足 putMode == PUT_NORM && accessOrder 的条件并执行 afterNodeAccess() 方法时，会将传入的 Node 对象从双向链表中移动到链表尾部。

正因如此，使用 LinkedHashMap 才能很容易地实现 LRU 缓存。每次从 LRU 缓存中获取到数据时，相当于是对缓存数据的一次访问，根据 LRU 的定义，自然要将最近使用过的缓存移动到最近位置，防止最近访问过的缓存被淘汰。

5.2 remove

LinkedHashMap 并未重写 remove() 方法，那这似乎不对啊。在 put 时会维护内部的双向链表，怎么到了 remove 就不维护了呢？

其中的逻辑也是相似的，LinkedHashMap 不是也没有重写 put() 方法，而是借由内部的钩子方法来维护内部的双向链表的吗？

HashMap 内部 remove() 的实现调用了 removeNode() 方法，该内部调用了名为 afterNodeRemoval() 的钩子方法。

当从 Map 中移除目标节点后，会将被移除的节点 node 传入 afterNodeRemoval() 方法中，以便子类实现其特殊逻辑。

LinkedHashMap 重写了 afterNodeRemoval() 方法，将被删除的节点从双向链表中移除，并链接其前驱节点与后继节点：

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 将被删除节点强转成 Entry 对象 p
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 断开 p 与链表的链接
    p.before = p.after = null;
    // p 没有前驱节点，它是链表的首节点
    if (b == null)
        // 被删除后，让 head 指向 p 的后继节点
        head = a;
    else
        // 否则，让前驱节点的 after 指针指向 p 的后继节点
        b.after = a;
    // p 没有后继节点，它是链表的尾节点
    if (a == null)
        // 被删除后，让 tail 指向 p 的前驱节点
        tail = b;
    else
        // 否则，让后继节点的 before 指针指向前驱节点
        a.before = b;
}

5.3 clear

clear() 的实现较为简单，几乎是沿用了 HashMap 的实现，只不过由于 LinkedHashMap 额外引入了 head 和 tail 指针，因此在实现 clear() 方法时，也需要将这两个指针置空：

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

5.4 containsKey

LinkedHashMap 并未重写 containsKey() 方法，继续沿用 HashMap 的实现：

public boolean containsKey(Object key) {
    return getNode(key) != null;
}

HashMap 中 containsKey() 方法的实现也很简单，和 get() 方法的实现类似，底层都是调用了 getNode() 方法。

getNode() 的实现也不难，相当于是 put() 方法的精简版。这也很好理解，put() 需要找到新 key 应该放到哪，getNode() 则是从现有数据中找出是否存在给定的 key，两者的实现主体都是 key 的搜索与定位。

一张图简单概括搜索过程：

flowchart TD
	a([开始])
	b[/给定的 key/]
	c[计算当前 key 所在的槽]
	d{"槽中第一个节点的 key<br/>是否等于给定的 key？"}
	e{"第一个节点后<br/>是否还有节点？"}
	f[尝试从红黑树或链表中搜索]
	g{"槽中没有节点？"}
	r1[返回找到的节点]
	r2[返回 null]
	r3[返回 null]
	z([结束])
	a-->b-->c-->g
	g-->|是|r2
	g-->|否|d
	d-->|是|r1
	r1-->z
	r2-->z
	r3-->z
	d-->|否|e
	e-->|否|r3
	e-->|是|f
	f-->z

5.5 containsValue

与 containsKey() 不同，LinkedHashMap 对 containsValue() 方法进行了重写。

在 HashMap 中，containsValue() 方法的实现由两层 for 循环完成，一层遍历底层 table 数组，一层遍历每个 Node 链表（当然也可能是红黑树）：

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (Node<K,V> e : tab) {
            for (; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

在遍历 table 数组的时候，不一定每个槽都有节点，这会产生一些无效的遍历。

由于 LinkedHashMap 内部维护了一条双向链表，直接遍历双向链表能够保证每个位置都是存在真实节点的，减少一定的遍历次数：

public boolean containsValue(Object value) {
    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;
}

6. 视图与遍历

对 Map 进行遍历的方式有三种，分别是对 key、对 value 和对 Entry 进行遍历。

在介绍具体的实现前，有必要介绍下 LinkedHashMap 内部众多的内部类。

6.1 迭代器

LinkedHashMap 内部有三种迭代器的实现，它们都有一个公共的基类 —— LinkedHashIterator。

LinkedHashIterator 是一个抽象类，并且支持还支持反转。

LinkedHashIterator 定义了 4 个成员变量：

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    boolean reversed;
	// --snip--
}

• next：下一个节点
• current：当前节点
• expectedModCount：期望的 modCount 值，这个值将与 HashMap 内部的 modCount 进行比较，当两者不相等时，抛出 ConcurrentModificationException
• reversed：是否反转。无特殊情况下，从 head 开始迭代。如果设置为反转，则是从 tail 开始迭代

LinkedHashIterator 仅提供一个构造函数：

LinkedHashIterator(boolean reversed) {
    this.reversed = reversed;
    // 如果需要反转，从 tail 开始迭代，否则从 head 开始
    next = reversed ? tail : head;
    expectedModCount = modCount;
    current = null;
}

LinkedHashIterator 内置了三个被 final 修饰的方法，它们的签名与 Iterator 接口中的三个方法类似。

首先是 hasNext()，判断是否还有下一个节点：

public final boolean hasNext() {
    return next != null;
}

然后是 nextNode()，获取迭代的下一个节点：

final LinkedHashMap.Entry<K,V> nextNode() {
    // 获取迭代的下一个节点
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 这个节点不能是 null
    if (e == null)
        throw new NoSuchElementException();
    // 设置当前迭代的节点是 e
    current = e;
    // 根据 reversed 获取新的下一个节点
    next = reversed ? e.before : e.after;
    // 返回 e
    return e;
}

最后是 remove()，在迭代过程中删除当前迭代的节点：

public final void remove() {
    // 获取当前迭代的节点
    Node<K,V> p = current;
    // 这个节点不能是 null
    if (p == null)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 设置当前迭代的节点是 null
    current = null;
    // 调用 removeNode，删除节点
    removeNode(p.hash, p.key, null, false, false);
    // 更新 expectedModCount
    expectedModCount = modCount;
}

三种迭代器的作用对象是 key、value 和 Entry：

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    LinkedKeyIterator(boolean reversed) { super(reversed); }
    public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    LinkedValueIterator(boolean reversed) { super(reversed); }
    public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    LinkedEntryIterator(boolean reversed) { super(reversed); }
    public final Map.Entry<K,V> next() { return nextNode(); }
}

实现比较简单，不再赘述。

6.2 视图

LinkedHashMap 内部提供了三种视图，分别是 key 的视图、value 的视图和 Entry 的视图，它们对应下列三个内部类：

• LinkedKeySet
• LinkedValues
• LinkedEntrySet

它们都允许传入 boolean 类型的 reversed 值，表示是否需要对该视图进行反转。

以 LinkedKeySet 为例：

final class LinkedKeySet extends AbstractSet<K> implements SequencedSet<K> {
    final boolean reversed;
    LinkedKeySet(boolean reversed)          { this.reversed = reversed; }
    
    // --snip--
}

继承 AbstractSet 并实现 SequencedSet 接口，内部部分方法实现与 LinkedHashMap 一致，比如：

public final int size()                 { return size; }
public final void clear()               { LinkedHashMap.this.clear(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
    return removeNode(hash(key), key, null, false, true) != null;
}

重写的 iterator() 方法返回前文中对应的迭代器：

public final Iterator<K> iterator() {
    return new LinkedKeyIterator(reversed);
}

因为 reversed 的存在，在 get 或 remove 是都需要进行判断。如果 reversed == true，getFirst() 方法应该返回链表 尾 节点的 key，getLast() 则应该返回链表 首 节点的 key：

public final K getFirst() { return nsee(reversed ? tail : head).key; }
public final K getLast() { return nsee(reversed ? head : tail).key; }

视图的遍历也会受到 reversed 的影响，它将决定是从 head 开始遍历，还是从 tail 开始遍历链表：

public final void forEach(Consumer<? super K> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    if (reversed) {
        // 如果反转，从 tail 开始遍历
        for (LinkedHashMap.Entry<K,V> e = tail; e != null; e = e.before)
            action.accept(e.key);
    } else {
        // 否则还是正常从 head 开始遍历
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key);
    }
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

此外，这些视图内部也都会有一个 reversed() 方法的实现，同样根据不同的 reversed 值有不同的实现，遵循“负负得正”：

public SequencedSet<K> reversed() {
    if (reversed) {
        return LinkedHashMap.this.sequencedKeySet();
    } else {
        return new LinkedKeySet(true);
    }
}

6.3 获取视图

LinkedHashMap 内部有多达 6 种获取不同视图的方式。

如果按照作用对象进行分组，可以分成三组，用于获取 key、value 和 Entry 的视图。

以获取 key 的视图为例，提供了 keySet() 和 sequencedKeySet() 两个方法：

ublic Set<K> keySet() {
    return sequencedKeySet();
}

public SequencedSet<K> sequencedKeySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        SequencedSet<K> sks = new LinkedKeySet(false);
        keySet = sks;
        return sks;
    } else {
        // The cast should never fail, since the only assignment of non-null to keySet is
        // above, and assignments in AbstractMap and HashMap are in overridden methods.
        return (SequencedSet<K>) ks;
    }
}

sequencedKeySet() 方法是 JDK21 中新增的，来源于实现的顺序集合 SequencedMap 接口。

这两个方法将从 head 开始遍历整个 LinkedHashMap 的 key。

一个表格概括获取视图的相关 API：

	来源于 Map	来源于 SequencedMap
key 的视图	keySet	sequencedKeySet
value 的视图	values	sequencedValues
Entry 的视图	entrySet	sequencedEntrySet

6.4 遍历与替换

LinkedHashMap 本身的遍历与替换逻辑很类似，都是从 head 开始遍历双向链表：

public void forEach(BiConsumer<? super K, ? super V> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    if (function == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        e.value = function.apply(e.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

6.5 ReversedLinkedHashMapView

ReversedLinkedHashMapView 是 LinkedHashMap 的一个静态嵌套类，它能够通过一个 LinkedHashMap 实例进行构造：

static class ReversedLinkedHashMapView<K, V> extends AbstractMap<K, V>
                                             implements SequencedMap<K, V> {
    final LinkedHashMap<K, V> base;

    ReversedLinkedHashMapView(LinkedHashMap<K, V> lhm) {
        base = lhm;
    }
	// --snip--
}

ReversedLinkedHashMapView 也继承了 AbstractMap 并实现 SequencedMap，这和 LinkedHashMap 很类似，但是其内部与顺序相关的实现都与 LinkedHashMap 相反，比如：

public Set<K> keySet() {
   return base.sequencedKeySet().reversed();
}
public V putFirst(K k, V v) {
    return base.putLast(k, v);
}

public V putLast(K k, V v) {
    return base.putFirst(k, v);
}

正因如此，LinkedHashMap 能够借助 ReversedLinkedHashMapView 实现反转：

public SequencedMap<K, V> reversed() {
    return new ReversedLinkedHashMapView<>(this);
}

7. 总结

1. LinkedHashMap 是 HashMap 的子类，在 JDK21 中还实现了 SequencedMap 接口，使其具备顺序集合的相关能力；
2. LinkedHashMap 内部维护了一个双向链表，根据构造 LinkedHashMap 时传入的 accessOrder 值，使得 LinkedHashMap 具备不同的迭代顺序；
3. 当 accessOrder 的值是 true 时，LinkedHashMap 将按照访问顺序迭代，借由此，可以很轻松实现 LRU 缓存；
4. LinkedHashMap 并没有重写 HashMap 中的 put() 和 remove() 方法，而是重写了这两个方法中调用的钩子方法，并实现自身相较于 HashMap 的增强。