🔍 深入浅出：LinkedHashMap 源码解析🧑‍💻

前言：认识 LinkedHashMap，背后的秘密武器 🔐

在 Java 中，LinkedHashMap 是一个非常重要且常用的类，它不仅继承自 HashMap，还能保持插入顺序，或者按访问顺序来迭代元素。简单来说，LinkedHashMap 结合了 哈希表 和 链表 的优势，既具备了 HashMap 的高效查找性能，又能保持元素的顺序，真的是一个性能与便利性兼具的完美选择。

那么，为什么我们要深入了解 LinkedHashMap 的源码呢？除了它的基本用法，深入源码还能帮助我们理解它是如何工作的，并且掌握如何在性能优化、数据结构选择等方面做得更好。接下来，我们就带着好奇心，探索一下 LinkedHashMap 背后的源码魔法！🔮

1. LinkedHashMap 概述：结构与特点

LinkedHashMap 继承自 HashMap，所以它与 HashMap 大体相同，都使用哈希表来存储数据。它的特殊之处在于它引入了链表来维护元素的顺序。可以选择通过插入顺序（默认）或访问顺序来排序，适用于需要记录元素顺序的场景。

LinkedHashMap 的结构

LinkedHashMap 主要由两个部分组成：

• 哈希表部分：存储键值对的散列数据结构，与 HashMap 相似。
• 双向链表部分：用于维护插入顺序或访问顺序，链表的每个节点存储了 Entry 对象，包含键值对和前后指针。

简单来说，LinkedHashMap 是一个结合了哈希表和双向链表的复合数据结构，在保证高效查找的同时，也保证了插入顺序或访问顺序。

2. LinkedHashMap 的核心字段

LinkedHashMap 源码剖析：主要字段

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    // 双向链表的头和尾
    private transient LinkedHashMap.Entry<K,V> head;
    private transient LinkedHashMap.Entry<K,V> tail;
    
    // 排序模式（插入顺序或访问顺序）
    private final boolean accessOrder;
    
    // 其他继承自 HashMap 的字段
}

这个代码片段展示了 LinkedHashMap 类的一个简化版本，它继承自 HashMap 并增加了链表支持，用于保持元素的顺序。LinkedHashMap 是 Java 中的一种特殊的 Map 实现，它不仅继承了 HashMap 的特性，还引入了双向链表来保持元素的插入顺序或访问顺序。

下面是该代码片段的详细解析：

1. 类继承关系

public class LinkedHashMap<K,V> extends HashMap<K,V> {

LinkedHashMap 继承自 HashMap，这意味着它具有 HashMap 的所有功能，如键值对存储、快速查找等。

2. 双向链表的头和尾

private transient LinkedHashMap.Entry<K,V> head;
private transient LinkedHashMap.Entry<K,V> tail;

head 和 tail 分别指向链表的头节点和尾节点。LinkedHashMap 使用一个双向链表来维护元素的顺序（插入顺序或访问顺序）。这些字段是 transient 的，意味着它们不会被序列化。

• head：指向链表的第一个元素。
• tail：指向链表的最后一个元素。

3. 排序模式

private final boolean accessOrder;

accessOrder 是一个布尔值，控制排序的方式：

• 插入顺序：如果 accessOrder 为 false，则保持元素的插入顺序。
• 访问顺序：如果 accessOrder 为 true，则按元素的访问顺序进行排序（即，每次访问一个元素后，它会被移动到链表的尾部）。

这个特性在实现最近最少使用（LRU）缓存时非常有用。

4. 双向链表节点（Entry 类）

尽管 Entry 类没有出现在这个片段中，但我们可以推测它的定义。这是 LinkedHashMap 的一个内部类，用于表示链表中的每个节点。Entry 类通常包含：

• key：存储键。
• value：存储值。
• next：指向下一个节点。
• previous：指向前一个节点。

双向链表中的每个节点都包含对前后节点的引用，这样可以从链表的两端进行遍历。

5. 继承自 HashMap 的功能

LinkedHashMap 继承自 HashMap，因此它也具备 HashMap 的所有功能，包括：

• 键值对存储：存储键值对（put、get 方法）。
• 去重：根据键去重，保证每个键唯一。
• 性能：在大多数情况下，LinkedHashMap 和 HashMap 的性能差别不大，LinkedHashMap 仅在元素顺序维护时稍微开销更大。

6. 常见方法

LinkedHashMap 类通常会重写一些方法，以支持链表操作：

• put(K key, V value)：将一个键值对插入到 LinkedHashMap 中。插入时会更新链表的顺序。
• get(Object key)：获取指定键的值，并根据 accessOrder 可能会更新链表顺序。
• remove(Object key)：删除指定键的元素，并更新链表。
• iterator()：返回一个迭代器，用于遍历 LinkedHashMap 的元素。

7. 总结

• 插入顺序 vs 访问顺序：LinkedHashMap 的主要特点是它能够在迭代时保持插入顺序，或者如果启用访问顺序，则根据访问顺序进行迭代。这样就使得 LinkedHashMap 成为一个非常适合缓存等场景的类。

• 性能：与 HashMap 相比，LinkedHashMap 由于维护了双向链表，所以它在插入、删除和查询操作时稍微有些额外的开销。不过，它在元素的顺序维护上非常有用，尤其在需要访问顺序时非常高效。

应用场景：常用于缓存实现、LRU缓存策略，或者需要保持元素顺序的场合。

1. head 和 tail 字段

这两个字段分别指向双向链表的头部和尾部。它们用于维护插入顺序或访问顺序（取决于 accessOrder 字段）。head 指向链表的第一个元素，tail 指向最后一个元素，通过这些指针可以快速进行遍历操作。

2. accessOrder 字段

这是一个 boolean 类型的字段，用来表示 LinkedHashMap 的排序方式：

• 如果 accessOrder 为 false（默认值），则 LinkedHashMap 维护元素的插入顺序。
• 如果 accessOrder 为 true，则 LinkedHashMap 按照访问顺序（即最近访问的元素排在最前面）来维护元素的顺序。这个特性非常适合实现 LRU (Least Recently Used) 缓存。

3. Entry 类：存储元素的双向链表节点

LinkedHashMap 的每个元素其实是 Entry 对象，它不仅存储键值对，还包含前后指针。每个 Entry 节点都维护了以下信息：

static class Entry<K,V> extends HashMap.Entry<K,V> {
    // 前驱节点
    Entry<K,V> before;
    // 后继节点
    Entry<K,V> after;

    Entry(int hash, K key, V value, Entry<K,V> next) {
        super(hash, key, value, next);
    }
}

before 和 after

• before 指向当前元素的前一个元素。
• after 指向当前元素的下一个元素。

这些指针是 LinkedHashMap 保持顺序的核心，构成了双向链表。每当插入新元素或访问元素时，链表的结构会相应地调整。

4. 构造方法解析

LinkedHashMap 提供了几个构造方法，最常见的两个如下：

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    this.accessOrder = false; // 默认为插入顺序
}

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

• 第一个构造方法创建一个按照插入顺序排序的 LinkedHashMap。
• 第二个构造方法可以选择排序方式，accessOrder 为 true 时会按访问顺序排序，适合用于实现缓存等场景。

5. 插入操作：维护双向链表顺序

当我们向 LinkedHashMap 插入元素时，哈希表部分会进行键值对的存储操作，而双向链表部分则会根据插入顺序或访问顺序进行调整。

插入操作的源码解析

public V put(K key, V value) {
    Entry<K,V> e = getEntry(key);
    if (e != null) {
        // 如果元素已存在，更新值
        return e.setValue(value);
    }
    // 插入新元素
    modCount++;
    Entry<K,V> newEntry = new Entry<>(hash, key, value, null);
    linkNodeLast(newEntry);
    return super.put(key, value);
}

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

1. 插入前检查元素是否已存在：如果元素已经存在，就更新该元素的值并返回旧值。
2. 插入新元素：通过 linkNodeLast 方法将新元素添加到链表的末尾，并更新 head 和 tail。
3. 维护链表顺序：如果排序模式是插入顺序，则新元素插入到链表的末尾；如果排序模式是访问顺序，则会调整顺序。

这段代码展示了 LinkedHashMap 中 put 方法的实现，并且涉及到节点在双向链表中的插入操作。我们来逐步分析每个方法和它们如何配合工作。

1. put(K key, V value) 方法

public V put(K key, V value) {
    Entry<K,V> e = getEntry(key);  // 获取指定 key 对应的 Entry 节点
    if (e != null) {
        // 如果元素已存在，更新值
        return e.setValue(value);  // 如果找到元素，更新值并返回旧的值
    }
    // 插入新元素
    modCount++;  // 增加修改计数，通常用于检测并发修改
    Entry<K,V> newEntry = new Entry<>(hash, key, value, null);  // 创建新的 Entry 节点
    linkNodeLast(newEntry);  // 将新的 Entry 插入到双向链表的末尾
    return super.put(key, value);  // 调用父类的 put 方法，将元素插入到哈希表中
}

解析：

• put(K key, V value) 方法的主要作用是将一个 key 和 value 键值对插入到 LinkedHashMap 中，或者如果 key 已存在，则更新其对应的 value。
• 查找现有键值对：首先通过调用 getEntry(key) 获取当前 key 对应的 Entry（如果存在的话）。
• 更新已存在元素：如果找到该 Entry，则通过 setValue(value) 更新它的值，并返回旧的值。
• 插入新元素：如果 key 不存在，则创建一个新的 Entry 节点，并通过 linkNodeLast(newEntry) 将它插入到双向链表的尾部。然后调用父类 HashMap 的 put 方法将该键值对插入到哈希表中。

2. linkNodeLast(Entry<K,V> newEntry) 方法

private void linkNodeLast(Entry<K,V> newEntry) {
    final Entry<K,V> last = tail;  // 获取链表的尾节点
    tail = newEntry;  // 更新链表的尾节点为新的节点
    if (last == null) {
        head = newEntry;  // 如果链表为空（第一次插入元素），将 head 指向新节点
    } else {
        last.after = newEntry;  // 将尾节点的 "after" 指针指向新节点
        newEntry.before = last;  // 将新节点的 "before" 指针指向旧的尾节点
    }
}

解析：

• linkNodeLast(Entry<K,V> newEntry) 方法负责将新的 Entry 节点插入到双向链表的末尾。
• 获取当前尾节点：final Entry<K,V> last = tail; 获取当前链表的尾节点（即 tail）。
• 更新尾节点：将 tail 指向新的节点 newEntry。
• 如果链表为空（即 last == null）：说明这是第一次插入节点，因此需要将 head 和 tail 都指向新节点。
• 如果链表不为空（即 last != null）：将旧的尾节点的 after 指针指向新节点，并将新节点的 before 指针指向旧的尾节点。这确保了双向链表的正确连接。

3. 双向链表的结构

LinkedHashMap 中通过维护一个双向链表来保持元素的插入顺序或者访问顺序（具体取决于构造时的 accessOrder 参数）。双向链表中的每个节点（Entry）包含两个指针：

• before：指向当前节点的前驱节点。
• after：指向当前节点的后继节点。

在插入一个新的 Entry 时，linkNodeLast 方法确保新的节点始终被插入到链表的末尾，同时通过 before 和 after 两个指针维护链表的顺序。

4. 总结

• put 方法用于将一个新的键值对插入 LinkedHashMap，并根据是否已经存在该 key 来决定是插入新节点还是更新现有节点的值。
• linkNodeLast 方法用于将新创建的 Entry 节点插入到双向链表的末尾，维护链表的顺序。
• 双向链表结构通过 before 和 after 两个指针高效地管理节点之间的连接，确保元素的顺序得以保持。

这些方法结合起来，使得 LinkedHashMap 在保持键值对顺序的同时，还能提供高效的查找和更新操作。

6. 删除操作：移除元素时调整链表

当删除一个元素时，LinkedHashMap 会移除哈希表中的键值对，并同时更新双向链表中的指针，保持链表的一致性。

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.getValue());
}

void removeNode(Entry<K,V> e) {
    if (e.before == null) {
        head = e.after;
    } else {
        e.before.after = e.after;
    }
    if (e.after == null) {
        tail = e.before;
    } else {
        e.after.before = e.before;
    }
}

1. 删除元素：通过 removeEntryForKey 方法找到要删除的元素，然后移除。
2. 调整链表：调用 removeNode 方法调整链表中的前后指针，确保链表的完整性。

这个代码片段展示了 LinkedHashMap 类中的 remove 和 removeNode 方法的实现。我们来逐步解析每个方法的作用和细节。

1. remove(Object key) 方法

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);  // 查找并移除与 key 对应的节点
    return (e == null ? null : e.getValue());  // 如果找到了节点，返回它的值，否则返回 null
}

解析：

• remove(Object key) 方法的作用是从 LinkedHashMap 中移除与指定 key 关联的键值对，并返回对应的值。如果没有找到该 key，则返回 null。
• 具体实现通过调用 removeEntryForKey(key) 来查找并移除与 key 关联的 Entry 节点。removeEntryForKey 方法通常会在 HashMap 中查找指定 key 并移除对应的 Entry。
• 如果找到该节点，则返回该节点的值（通过 e.getValue()），否则返回 null。

removeEntryForKey(key):

• 该方法通常会从哈希表中找到指定的节点，并执行移除操作。

2. removeNode(Entry<K,V> e) 方法

void removeNode(Entry<K,V> e) {
    if (e.before == null) {
        head = e.after;  // 如果该节点是链表的头节点，更新头节点为该节点的后继节点
    } else {
        e.before.after = e.after;  // 将该节点的前驱节点的 "next" 指针指向该节点的后继节点
    }
    if (e.after == null) {
        tail = e.before;  // 如果该节点是链表的尾节点，更新尾节点为该节点的前驱节点
    } else {
        e.after.before = e.before;  // 将该节点的后继节点的 "previous" 指针指向该节点的前驱节点
    }
}

解析：

removeNode(Entry<K,V> e) 方法负责从双向链表中移除一个节点 e。在 LinkedHashMap 中，除了哈希表存储键值对外，还维护了一个双向链表（由 head 和 tail 节点指向链表的两端）来保持元素的顺序。移除一个节点时，涉及到更新链表中节点的前驱和后继节点的引用。

具体步骤：

• 如果节点 e 是头节点 (e.before == null)，则将链表的头节点 head 更新为 e 的后继节点（即 e.after）。
• 如果节点 e 不是头节点 (e.before != null)，则更新 e 的前驱节点的 after 指针，指向 e 的后继节点（即 e.after）。
• 如果节点 e 是尾节点 (e.after == null)，则将链表的尾节点 tail 更新为 e 的前驱节点（即 e.before）。
• 如果节点 e 不是尾节点 (e.after != null)，则更新 e 的后继节点的 before 指针，指向 e 的前驱节点（即 e.before）。

3. 链表的操作

LinkedHashMap 使用了一个双向链表来维护元素的顺序。每个 Entry 节点包含了两个指针：

• before：指向当前节点的前一个节点。
• after：指向当前节点的后一个节点。

通过 before 和 after 两个指针，可以很方便地在常数时间内（O(1)）删除节点并更新链表结构。

4. 总结

• remove(Object key) 方法从 LinkedHashMap 中移除指定 key 的元素，并返回对应的值。
• removeNode(Entry<K,V> e) 方法则负责实际从双向链表中移除指定的节点，并更新链表的 head 和 tail 引用。
• LinkedHashMap 利用双向链表维护元素的顺序，因此，移除节点时需要同时更新前驱和后继节点的链接。

这两个方法一起协作，实现了从 LinkedHashMap 中有效地移除元素，同时保持双向链表的正确顺序。

7. 总结：LinkedHashMap 的奥秘

通过对 LinkedHashMap 源码的深入剖析，我们发现它不仅继承了 HashMap 的高效查找能力，还通过双向链表维护了元素的顺序。无论是插入顺序还是访问顺序，它都能帮助我们方便地处理有序的数据集合。

• 哈希表 提供了高效的查找操作；
• 双向链表 保证了元素的顺序，不管是插入顺序还是访问顺序。

通过理解这些底层实现，我们可以更好地在实际开发中使用 LinkedHashMap，并优化代码的执行效率。

🧧福利赠与你🧧

  无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学SpringBoot」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门SpringBoot，就像滚雪球一样，越滚越大， 无边无际，指数级提升。

最后，如果这篇文章对你有所帮助，帮忙给作者来个一键三连，关注、点赞、收藏，您的支持就是我坚持写作最大的动力。

同时欢迎大家关注公众号:「猿圈奇妙屋」 ，以便学习更多同类型的技术文章，免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

✨️ Who am I?

我是bug菌，CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家，C站博客之星Top30，华为云2023年度十佳博主，掘金多年度人气作者Top40，掘金等各大社区平台签约作者，51CTO年度博主Top12，掘金/InfoQ/51CTO等社区优质创作者；全网粉丝合计 30w+；更多精彩福利点击这里；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试真题、4000G PDF电子书籍、简历模板等海量资料，你想要的我都有，关键是你不来拿。

-End-