假设一个Map里依次放了A、B、C。调用get(A)只是读值没有新增键也没有删除键下次遍历顺序会变吗对默认的LinkedHashMap仍是A、B、C。开启访问顺序以后却变成B、C、A初始顺序A - B - C get(A) B - C - A // 开启访问顺序时查找还是那次查找为什么顺序变了如果把它当缓存下一次放入D时又该淘汰谁答案不是重新排列哈希桶而是在查找用的连接之外还维护了一条决定遍历顺序的双向链。先用具体操作区分“插入先后”和“访问先后”再看链怎样移动最后做容量3的学习版LRU。1. 先分清顺序由什么决定HashMap 不承诺按插入顺序遍历不代表每次遍历都要洗牌。桶位置与哈希值、容量等有关同一组数据反复运行可能得到相同顺序这不能变成业务依赖。同样不能把某次输出中null排在第一位写成“HashMap保证null最先输出”。LinkedHashMap 的插入顺序模式则有明确承诺新键放在顺序链的末尾已有键改值不等于重新插入。下面每一行是在上一行的结果上继续操作初始为A1, B2, C3插入顺序模式中的操作操作后的键顺序发生了什么get(A)A、B、C查值不改变插入先后put(B,20)A、B、C原B的值变为20不重新排队remove(B)再put(B,2)A、C、B旧映射删除新映射插在末尾put(null,0)A、C、B、nullnull作为新键也按插入先后处理“覆盖一个键”和“删掉后再插入一个键”不是一回事。这是理解插入顺序最容易漏掉的边界。2. 一份条目两套关系读源码时先分清节点上的指针用途普通条目的next属于哈希桶中的链LinkedHashMap增加的before/after属于维护遍历顺序的双向链。它们不是同一条链发生哈希碰撞也不决定谁最早被访问。本轮源码的普通条目结构可以概括为Entry extends HashMap.Node hash / key / value / next 用于哈希查找及桶内连接 before / after 用于全局遍历顺序 head 顺序链第一个条目 tail 顺序链最后一个条目这只是普通节点的结构提要不是可编译的JDK源码也没有展开树化桶的全部实现。新条目插入时可以沿这条路径看HashMap.put→putVal→ 动态调用LinkedHashMap.newNode→linkNodeLast。桶里保存这个节点顺序链也链接这个节点而不是另外复制一份键值对。linkNodeLast保存原tail再把新节点设为tail原链为空就同时设置head否则连接“原tail.after → 新节点”和“新节点.before → 原tail”。所以HashMap的查找机制可以继续使用遍历顺序却由另一套连接维护。3. 访问顺序把“访问”拆成具体操作构造方式只多一个开关LinkedHashMapString, Integer map new LinkedHashMap(16, 0.75f, true);true表示访问顺序默认模式是插入顺序。再从A、B、C开始连续做下面操作操作操作后的顺序是否成为最近访问get(A)B、C、A命中AA移到尾部put(B,20)C、A、B已有B更新B移到尾部containsKey(C)C、A、B只判断存在不刷新顺序get(missing)C、A、B没有命中条目无节点可移动replace(C,999,30)C、A、B原值不是999替换失败不刷新replace(C,3,30)A、B、C替换成功C移到尾部remove(B)A、CB离开容器不是移动到尾部这里的“最近”是访问先后不是访问次数。头部不是“访问频率最低”而是当前条目里最久没有被这类操作访问的那个。LRU与LFU也因此不是同一种策略。图只画顺序链和操作前后状态不画桶的位置这是本文新增的示意图不是调试器拍到的内存布局。表中的操作结果由文末程序实际核对。其他方法也可能产生访问不能把上表当成完整API清单准确条件见Java 17 LinkedHashMap文档。尤其是replace的“成功替换”条件不能省略。4. get为什么能改链迭代器为什么会受影响LinkedHashMap.get先找到节点没找到就返回null。命中且启用访问顺序时调用afterNodeAccess然后返回值。本轮源码里的afterNodeAccess还有一个条件节点不是当前tail才需要断开原位置并接到尾部。如果节点就是tail顺序已经正确不必重新连一次。把中间节点B移尾可以分成两步理解先让B的前后邻居互相连接再让原tail与B相连并更新tail。移动head时还要更新head。键值没变桶也不需要重新按访问先后排列变化的是遍历用的连接。重新连链时本轮实现还递增modCount。于是下面的“读”可能使旧迭代器失效即使程序只有一个线程IteratorString iterator map.keySet().iterator(); map.get(A); // 前提A存在、开启访问顺序、A不是tail iterator.next();在本轮的A、B、C样本中最后一句抛出ConcurrentModificationException换成读取当前尾部C旧迭代器的第一次next仍得到A。这是指定实现下的对照不是“所有get都必然抛异常”。异常是发现错误用法的线索不是并发安全机制更不能据此认为不抛异常就线程安全。遍历时需要值通常应使用entrySet中当前条目的getValue别再对同一个访问顺序map逐键调用get并发时另行设计同步边界。5. true只负责顺序不会自动限制容量给普通访问顺序map连续放A、B、C、D本轮size为4。构造参数16也不是“最多16条”它是初始容量参数不是缓存淘汰限额。学习版LRU还需要一个明确策略每次新增条目后如果size() limit允许容器删掉头部。完整子类在附录中核心只有Override protected boolean removeEldestEntry(Map.EntryString, Integer eldest) { return size() limit; }容量3的过程是A、B、C → get(A)得到B、C、A → put(D)暂时形成B、C、A、D → 超限删除B → C、A、D。这里用不是若达到容量3就删除只能保留2条。沿源码看是afterNodeInsertion在符合条件时询问removeEldestEntry(head)。默认策略返回false子类才定义容量限制。已有键更新和新增节点是不同路径不能写成“每次调用put一定都触发容量回调”。附录还测试limit0时新增条目立即被淘汰负limit由子类拒绝。这个缓存仅是单线程、按条目数限额的演示没有过期、按内存计费、加载合并或并发保证不能直接作为生产缓存方案。6. 现在再看这个get它没有改变映射数量却可能改变一条记录在顺序链中的位置。“只读”如果指不改键值是一回事如果指不改内部结构就是另一回事。这也解释了为什么旧迭代器可能失效。而LRU不是把最早插入的记录扔掉A刚被读取就移到最近访问的一端。此时加入D应该淘汰的是更久没被访问的B。访问顺序提供次序容量回调提供淘汰条件两部分合起来才是这个学习版缓存。下面的代码与测试用于核对这些操作不是要把每种边界都背成API口诀。附录一验证程序怎样避免“打印一下就算对”每次读取keySet复制出当前顺序再与手工推导的期望列表比较同时核对更新值、缺失返回、替换成功与失败、淘汰结果和迭代异常。测试中的观察过程不调用get逐项打印否则观察本身会改变访问顺序。每个测试组重新创建容器组内操作顺序与前文表格一致。容量边界与失败替换用于反驳两个常见错误“达到容量就删”和“replace一定刷新顺序”。检查使用显式AssertionError不依赖Java默认关闭的assert开关。这些是固定小样本不是完整集合兼容性测试更不是性能基准。它能把本文结论与可执行条件绑在一起但没有证明所有并发或树化场景。附录二完整可运行源码实测使用Amazon Corretto 17.0.12运行时17.0.127-LTS源码核对来自该安装目录的lib/src.zip。涉及内部方法与modCount的描述限定于这个实现本篇实验不需要反射也不修改JDK。需要JDK17下面文件命名为LinkedOrderLab.java在新建目录执行javac -encoding UTF-8 LinkedOrderLab.java java LinkedOrderLab程序打印运行时版本、每项PASS以及最后的检查总数任何不符合预期的结果都会异常退出。无需第三方库不连接数据库或网络。本轮实际输出节选如下省略了其余PASS行runtime17.0.127-LTS PASS access get(A) [B, C, A] PASS access put existing B [C, A, B] PASS containsKey does not access [C, A, B] PASS failed replace does not access [C, A, B] PASS LRU after put(D) [C, A, D] CHECKS_PASSED24我另外把淘汰条件故意改成size() limit再运行同一套检查程序在LRU after get(A)处报错实际只剩B、C。因为插入第三条时就误删了A之后get(A)无法把它移尾。这不是正确版本的输出而是用来确认测试能抓住错误的失败对照。import java.util.*; public class LinkedOrderLab { private static int checks; private static LinkedHashMapString, Integer sample(boolean access) { LinkedHashMapString, Integer map new LinkedHashMap(16, 0.75f, access); map.put(A, 1); map.put(B, 2); map.put(C, 3); return map; } private static void check(String label, boolean condition) { if (!condition) throw new AssertionError(label); checks; System.out.println(PASS label); } private static void order(String label, MapString, Integer map, String... keys) { ListString actual new ArrayList(map.keySet()); check(label actual, actual.equals(Arrays.asList(keys))); } static class Lru extends LinkedHashMapString, Integer { private final int limit; Lru(int limit) { super(16, 0.75f, true); if (limit 0) throw new IllegalArgumentException(negative limit); this.limit limit; } Override protected boolean removeEldestEntry(Map.EntryString, Integer eldest) { return size() limit; } } public static void main(String[] args) { System.out.println(runtime System.getProperty(java.runtime.version)); LinkedHashMapString, Integer insertion sample(false); insertion.get(A); order(insertion get(A), insertion, A, B, C); insertion.put(B, 20); order(insertion put existing B, insertion, A, B, C); check(updated value, insertion.get(B) 20); insertion.remove(B); insertion.put(B, 2); order(remove and reinsert B, insertion, A, C, B); insertion.put(null, 0); order(null inserted last, insertion, A, C, B, (String) null); LinkedHashMapString, Integer access sample(true); access.get(A); order(access get(A), access, B, C, A); access.put(B, 20); order(access put existing B, access, C, A, B); check(containsKey finds C, access.containsKey(C)); order(containsKey does not access, access, C, A, B); check(missing get returns null, access.get(missing) null); order(missing get does not access, access, C, A, B); check(failed replace returns false, !access.replace(C, 999, 30)); order(failed replace does not access, access, C, A, B); check(successful replace, access.replace(C, 3, 30)); order(successful replace accesses C, access, A, B, C); access.remove(B); order(remove unlinks B, access, A, C); LinkedHashMapString, Integer iterated sample(true); IteratorString iterator iterated.keySet().iterator(); iterated.get(A); boolean failed false; try { iterator.next(); } catch (ConcurrentModificationException expected) { failed true; } check(get non-tail invalidates old iterator in this runtime, failed); iterated sample(true); iterator iterated.keySet().iterator(); iterated.get(C); check(get tail does not relink in this runtime, iterator.next().equals(A)); LinkedHashMapString, Integer unlimited sample(true); unlimited.put(D, 4); check(accessOrder alone does not cap size, unlimited.size() 4); Lru cache new Lru(3); cache.put(A, 1); cache.put(B, 2); cache.put(C, 3); cache.get(A); order(LRU after get(A), cache, B, C, A); cache.put(D, 4); order(LRU after put(D), cache, C, A, D); check(B evicted and D retained, !cache.containsKey(B) cache.containsKey(D)); Lru zero new Lru(0); zero.put(A, 1); check(zero limit retains nothing, zero.isEmpty()); boolean negative false; try { new Lru(-1); } catch (IllegalArgumentException expected) { negative true; } check(negative limit rejected, negative); System.out.println(CHECKS_PASSED checks); } }