LinkedHashMap 有序原理详解

LinkedHashMap 的“有序”并非来自哈希表本身的排序能力，而是巧妙地在 HashMap 基础上额外维护了一条双向链表——默认按插入顺序将新节点追加至链表尾部，确保遍历时严格遵循插入顺序；当启用访问顺序模式（accessOrder=true）时，则在每次 get 或 put 等操作后将对应节点移至尾部，使头节点始终代表最近最少使用（LRU）项，从而天然支撑高效、简洁的 LRU 缓存实现；这种“哈希表负责快速查找，链表专注维护顺序”的职责分离设计，既保留了 HashMap 的高性能，又赋予了确定性遍历能力，是理解其底层原理与实用价值的关键所在。

LinkedHashMap 为什么能保持有序

它不是靠哈希表本身排序，而是额外维护了一条贯穿所有 Entry 的双向链表。HashMap 的数组+链表/红黑树结构负责快速查找，而这条独立的双向链表专门负责记录顺序——插入时追加到尾部，访问时（在特定模式下）移动到尾部，迭代时就按链表顺序走，自然就“有序”了。

插入顺序模式（默认行为）

这是 LinkedHashMap 的默认模式，accessOrder = false。每次调用 put 插入新键值对时，除了正常写入哈希表，还会把对应 Entry 节点链接到双向链表末尾：

• 新节点的 before 指向前一个尾节点
• 前一个尾节点的 after 指向新节点
• 更新 tail 指针指向新节点
• 若链表为空（首次插入），新节点同时成为 head 和 tail

因此遍历 entrySet 或 keySet 时，顺序严格等于插入顺序，哪怕哈希位置打乱也完全不影响。

访问顺序模式（LRU 缓存基础）

当构造时传入 true： new LinkedHashMap(16, 0.75f, true)，就启用访问顺序模式。accessOrder = true。此时只要对已有 key 执行 get、put（key 存在）、compute 等访问操作，对应 Entry 就会被移到双向链表末尾：

• 先从链表中“摘下”该节点（调整前后节点的 before/after 引用）
• 再把它“插入”到 tail 位置
• head 始终指向最近最少使用的（LRU）项，tail 指向最近刚访问的项

这个机制是实现 LRU 缓存的核心支撑，配合重写 removeEldestEntry 方法即可自动淘汰头节点。

底层结构的关键改动

LinkedHashMap 并没有另起炉灶，而是在 HashMap 基础上做了精准增强：

• Entry 类继承自 HashMap.Node，新增 before 和 after 字段，构成双向链表节点
• 重写 newNode 方法，在创建节点后立即调用 linkNodeLast 维护链表
• 重写 afterNodeAccess（访问时重排）、afterNodeInsertion（插入后钩子）等回调方法
• 保留 head 和 tail 引用，让链表操作 O(1) 完成

本质上，LinkedHashMap = HashMap（查得快） + 双向链表（排得稳），两者职责分离，互不干扰。

到这里，我们也就讲完了《LinkedHashMap 有序原理详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！