LinkedHashMap 源码分析

LinkedHashMap 简介 是 Java 提供的一个集合类，它继承自 ，并在 基础上维护一条双向链表，使得具备如下特性: 1. 支持遍历时会按照插入顺序有序进行迭代。 2. 支持按照元素访问顺序排序，适用于封装 LRU 缓存工具。 3. 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。 逻辑结构如下图所示，它是在 基础上在各个节点之间维护一条双向链表，使得原本散列在不同 bucket 上的节点、链表、红黑树有序关联起来。 LinkedHashMap 使用示例 插入顺序遍历 如下所示，我们按照顺序往 添加元素然后进行遍历。 输出： 可以看出， 的迭代顺序是和插入顺序一致的，这一点是 所不具备的。 访问顺序遍历 定义了排序模式 （boolean 类型，默认为 false），访问顺序则为 true，插入顺序则为 false。 为了实现访问顺序遍历，我们可以使用传入 属性的 构造方法，并将 设置为 true，表示其具备访问有序性。 输出： 可以看出， 的迭代顺序是和访问顺序一致的。 LRU 缓存 从上一个我们可以了解到通过 我们可以封装一个简易版的 LRU（ L east R ecently U sed，最近最少使用） 缓存，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。 具体实现思路如下： 继承 ; 构造方法中指定 为 true，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素； 重写 方法，该方法会返回一个 boolean 值，告知 是否需要移除链表首元素（缓存容量有限）。 测试代码如下，笔者初始化缓存容量为 3，然后按照次序先后添加 4 个元素。 输出： 从输出结果来看，由于缓存容量为 3，因此，添加第 4 个元素时，第 1 个元素会被删除。添加第 5 个元素时，第 2 个元素会被删除。 LinkedHashMap 源码解析 Node 的设计 在正式讨论 前，我们先来聊聊 节点 的设计，我们都知道 的 bucket 上的因为冲突转为链表的节点会在符合以下两个条件时会将链表转为红黑树: 1. 链表上的节点个数达到树化的阈值 7，即 。 2. bucket 的容量达到最小的树化容量即 。 🐛 修正（参见：issue 2147） ： 链表上的节点个数达到树化的阈值是 8 而非 7。因为源码的判断是从链表初始元素开始遍历，下标是从 0 开始的，所以判断条件设置为 8 1=7，其实是迭代到尾部元素时再判断整个链表长度大于等于 8 才进行树化操作。 而 是在 的基础上为 bucket 上的每一个节点建立一条双向链表，这就使得转为红黑树的树节点也需要具备双向链表节点的特性，即每一个树节点都需要拥有两个引用存储前驱节点和后继节点的地址，所以对于树节点类 的设计就是一个比较棘手的问题。 对此我们不妨来看看两者之间节点类的类图，可以看到: 1. 的节点内部类 基于 的基础上，增加 和 指针使节点具备双向链表的特性。 2. 的树节点 继承了具备双向链表特性的 的 。 很多读者此时就会有这样一个疑问，为什么 的树节点 要通过 获取双向链表的特性呢？为什么不直接在 上实现前驱和后继指针呢？ 先来回答第一个问题，我们都知道 是在 基础上对节点增加双向指针实现双向链表的特性，所以 内部链表转红黑树时，对应的节点会转为树节点 ,为了保证使用 时树节点具备双向链表的特性，所以树节点 需要继承 的 。 再来说说第二个问题，我们直接在 的节点 上直接实现前驱和后继指针，然后 直接继承 获取双向链表的特性为什么不行呢？其实这样做也是可以的。只不过这种做法会使得使用 时存储键值对的节点类 多了两个没有必要的引用，占用没必要的内存空间。 所以，为了保证 底层的节点类 没有多余的引用，又要保证 的节点类 拥有存储链表的引用，设计者就让 的节点 去继承 Node 并增加存储前驱后继节点的引用 、 ，让需要用到链表特性的节点去实现需要的逻辑。然后树节点 再通过继承 获取 、 两个指针。 但是这样做，不也使得使用 时的 多了两个没有必要的引用吗？这不也是一种空间的浪费吗？ 对于这个问题，引用作者的一段注释，作者们认为在良好的 算法时， 转红黑树的概率不大。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 变为 ，所以 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。 构造方法 构造方法有 4 个实现也比较简单，直接调用父类即 的构造方法完成初始化。 我们上面也提到了，默认情况下 为 false，如果我们要让 实现键值对按照访问顺序排序（即将最近未访问的元素排在链表首部、最近访问的元素移动到链表尾部），需要调用第 4 个构造方法将 设置为 true。 get 方法 方法是 增删改查操作中唯一一个重写的方法， 为 true 的情况下， 它会在元素查询完成之后，将当前访问的元素移到链表的末尾。 从源码可以看出， 的执行步骤非常简单: 1. 调用父类即 的 获取键值对，若为空则直接返回。 2. 判断 是否为 true，若为 true 则说明需要保证 的链表访问有序性，执行步骤 3。 3. 调用 重写的 将当前元素添加到链表末尾。 关键点在于 方法的实现，这个方法负责将元素移动到链表末尾。 从源码可以看出， 方法完成了下面这些操作: 1. 如果 为 true 且链表尾部不为当前节点 p，我们则需要将当前节点移到链表尾部。 2. 获取当前节点 p、以及它的前驱节点 b 和后继节点 a。 3. 将当前节点 p 的后继指针设置为 null，使其和后继节点 p 断开联系。 4. 尝试将前驱节点指向后继节点，若前驱节点为空，则说明当前节点 p 就是链表首节点，故直接将后继节点 a 设置为首节点，随后我们再将 p 追加到 a 的末尾。 5. 再尝试让后继节点 a 指向前驱节点 b。 6. 上述操作让前驱节点和后继节点完成关联，并将当前节点 p 独立出来，这一步则是将当前节点 p 追加到链表末端，如果链表末端为空，则说明当前链表只有一个节点 p，所以直接让 head 指向 p 即可。 7. 上述操作已经将 p 成功到达链表末端，最后我们将 tail 指针即指向链表末端的指针指向 p 即可。 可以结合这张图理解，展示了 key 为 13 的元素被移动到了链表尾部。 看不太懂也没关系，知道这个方法的作用就够了，后续有时间再慢慢消化。 newNode——新节点尾插链表 上文介绍了 如何将 已存在的节点 移动到链表尾部，那么 新插入的节点 是如何被添加到链表中的呢？ 答案在于 重写了 的 方法。当 插入新键值对时，会调用 创建节点对象， 在重写的方法中不仅创建了 节点，还额外调用了 将其链接到双向链表的尾部： 方法的实现如下： 这就是 LinkedHashMap 实现插入有序的核心机制 ：每次插入新节点时，通过重写 并调用 ，将新节点追加到双向链表尾部。这样遍历时从头节点 开始沿着 指针遍历，就能按插入顺序获取所有元素。 同理， 也重写了 方法，确保树节点插入时同样会被链接到链表尾部： remove 方法后置操作——afterNodeRemoval 并没有对 方法进行重写，而是直接继承 的 方法，为了保证键值对移除后双向链表中的节点也会同步被移除， 重写了 的空实现方法 。 我们可以看到从 继承来的 方法内部调用的 方法将节点从 bucket 删除后，调用了 。 从源码可以看出， 方法的整体操作就是让当前节点 p 和前驱节点、后继节点断开联系，等待 gc 回收，整体步骤为: 1. 获取当前节点 p、以及 p 的前驱节点 b 和后继节点 a。 2. 让当前节点 p 和其前驱、后继节点断开联系。 3. 尝试让前驱节点 b 指向后继节点 a，若 b 为空则说明当前节点 p 在链表首部，我们直接将 head 指向后继节点 a 即可。 4. 尝试让后继节点 a 指向前驱节点 b，若 a 为空则说明当前节点 p 在链表末端，所以直接让 tail 指针指向前驱节点 b 即可。 可以结合这张图理解，展示了 key 为 13 的元素被删除，也就是从链表中移除了这个元素。 看不太懂也没关系，知道这个方法的作用就够了，后续有时间再慢慢消化。 put 方法后置操作——afterNodeInsertion 同样的 并没有实现插入方法，而是直接继承 的所有插入方法交由用户使用，但为了维护双向链表访问的有序性，它做了这样两件事: 1. 重写 （上文提到过）,如果当前被插入的 key 已存在与 中，因为 的插入操作会将新节点追加至链表末尾，所以对于存在的 key 则调用 将其放到链表末端。 2. 重写了 的 方法，当 返回 true 时，会将链表首节点移除。 这一点我们可以在 的插入操作核心方法 中看到。 上述步骤的源码上文已经解释过了，所以这里我们着重了解一下 的工作流程，假设我们的重写了 ，当链表 超过 时，就返回 true。 以下图为例，假设笔者最后新插入了一个不存在的节点 19,假设 为 4，所以 返回 true，我们要将链表首节点移除。 移除的步骤很简单，查看链表首节点是否存在，若存在则断开首节点和后继节点的关系，并让首节点指针指向下一节点，所以 head 指针指向了 12，节点 10 成为没有任何引用指向的空对象，等待 GC。 从源码可以看出， 方法完成了下面这些操作: 1. 判断 是否为 true，只有为 true 才能说明可能需要将最年长的键值对（即链表首部的元素）进行移除，具体是否具体要进行移除，还得确定链表是否为空 ，以及 方法是否返回 true，只有这两个方法返回 true 才能确定当前链表不为空，且链表需要进行移除操作了。 2. 获取链表第一个元素的 key。 3. 调用 的 方法，该方法我们上文提到过，它会将节点从 的 bucket 中移除，并且 还重写了 中的 方法，所以这一步将通过调用 将元素从 的 bucket 中移除，并和 的双向链表断开，等待 gc 回收。 LinkedHashMap 和 HashMap 遍历性能比较 维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。这一点相比于 那种遍历整个 bucket 的方式来说，高效许多。 这一点我们可以从两者的迭代器中得以印证，先来看看 的迭代器，可以看到 迭代键值对时会用到一个 方法，该方法会返回 next 指向的下一个元素，并会从 next 开始遍历 bucket 找到下一个 bucket 中不为空的元素 Node。 相比之下 的迭代器则是直接使用通过 指针快速定位到当前节点的后继节点，简洁高效许多。 为了验证笔者所说的观点，笔者对这两个容器进行了压测，测试插入 1000w 和迭代 1000w 条数据的耗时，代码如下: 从输出结果来看，因为 需要维护双向链表的缘故，插入元素相较于 会更耗时，但是有了双向链表明确的前后节点关系，迭代效率相对于前者高效了许多。不过，总体来说却别不大，毕竟数据量这么庞大。 LinkedHashMap 常见面试题 什么是 LinkedHashMap？ 是 Java 集合框架中 的一个子类，它继承了 的所有属性和方法，并且在 的基础重写了 、 、 方法。使之拥有顺序插入和访问有序的特性。 LinkedHashMap 如何按照插入顺序迭代元素？ 按照插入顺序迭代元素是它的默认行为。 内部维护了一个双向链表，用于记录元素的插入顺序。因此，当使用迭代器迭代元素时，元素的顺序与它们最初插入的顺序相同。 LinkedHashMap 如何按照访问顺序迭代元素？ 可以通过构造函数中的 参数指定按照访问顺序迭代元素。当 为 true 时，每次访问一个元素时，该元素会被移动到链表的末尾，因此下次访问该元素时，它就会成为链表中的最后一个元素，从而实现按照访问顺序迭代元素。 LinkedHashMap 如何实现 LRU 缓存？ 将 设置为 true 并重写 方法当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 返回 true 时，视为缓存已满， 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。 LinkedHashMap 和 HashMap 有什么区别？ 和 都是 Java 集合框架中的 Map 接口的实现类。它们的最大区别在于迭代元素的顺序。 迭代元素的顺序是不确定的，而 提供了按照插入顺序或访问顺序迭代元素的功能。此外， 内部维护了一个双向链表，用于记录元素的插入顺序或访问顺序，而 则没有这个链表。因此， 的插入性能可能会比 略低，但它提供了更多的功能并且迭代效率相较于 更加高效。 参考文献 LinkedHashMap 源码详细分析（JDK1.8）:<https://www.imooc.com/article/22931 HashMap 与 LinkedHashMap:<https://www.cnblogs.com/Spground/p/8536148.html 源于 LinkedHashMap 源码: <https://leetcode.cn/problems/lru cache/solution/yuan yu linkedhashmapyuan ma by jeromememory/ 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。