企业官网建设流程全解析

假设一个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 的插入顺序模式则有明确承诺：新键放在顺序链的末尾，已有键改值不等于重新插入。

下面每一行是在上一行的结果上继续操作，初始为A=1, B=2, C=3：

“覆盖一个键”和“删掉后再插入一个键”不是一回事。这是理解插入顺序最容易漏掉的边界。

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. 访问顺序：把“访问”拆成具体操作

构造方式只多一个开关：

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);

true表示访问顺序，默认模式是插入顺序。再从A、B、C开始，连续做下面操作：

这里的“最近”是访问先后，不是访问次数。头部不是“访问频率最低”，而是当前条目里最久没有被这类操作访问的那个。LRU与LFU也因此不是同一种策略。

图只画顺序链和操作前后状态，不画桶的位置；这是本文新增的示意图，不是调试器拍到的内存布局。表中的操作结果由文末程序实际核对。

其他方法也可能产生访问，不能把上表当成完整API清单；准确条件见Java 17 LinkedHashMap文档。尤其是replace的“成功替换”条件，不能省略。

4. get为什么能改链？迭代器为什么会受影响？

LinkedHashMap.get先找到节点；没找到就返回null。命中且启用访问顺序时调用afterNodeAccess，然后返回值。

本轮源码里的afterNodeAccess还有一个条件：节点不是当前tail，才需要断开原位置并接到尾部。如果节点就是tail，顺序已经正确，不必重新连一次。

把中间节点B移尾，可以分成两步理解：先让B的前后邻居互相连接，再让原tail与B相连，并更新tail。移动head时还要更新head。键值没变，桶也不需要重新按访问先后排列，变化的是遍历用的连接。

重新连链时，本轮实现还递增modCount。于是下面的“读”可能使旧迭代器失效，即使程序只有一个线程：

Iterator<String> 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.Entry<String, 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一定都触发容量回调”。

附录还测试limit=0时新增条目立即被淘汰，负limit由子类拒绝。这个缓存仅是单线程、按条目数限额的演示：没有过期、按内存计费、加载合并或并发保证，不能直接作为生产缓存方案。

6. 现在再看这个get

它没有改变映射数量，却可能改变一条记录在顺序链中的位置。“只读”如果指不改键值，是一回事；如果指不改内部结构，就是另一回事。这也解释了为什么旧迭代器可能失效。

而LRU不是把最早插入的记录扔掉：A刚被读取，就移到最近访问的一端。此时加入D，应该淘汰的是更久没被访问的B。访问顺序提供次序，容量回调提供淘汰条件，两部分合起来才是这个学习版缓存。

下面的代码与测试用于核对这些操作，不是要把每种边界都背成API口诀。

附录一：验证程序怎样避免“打印一下就算对”？

每次读取keySet复制出当前顺序，再与手工推导的期望列表比较；同时核对更新值、缺失返回、替换成功与失败、淘汰结果和迭代异常。测试中的观察过程不调用get逐项打印，否则观察本身会改变访问顺序。

每个测试组重新创建容器，组内操作顺序与前文表格一致。容量边界与失败替换用于反驳两个常见错误：“达到容量就删”和“replace一定刷新顺序”。检查使用显式AssertionError，不依赖Java默认关闭的assert开关。

这些是固定小样本，不是完整集合兼容性测试，更不是性能基准。它能把本文结论与可执行条件绑在一起，但没有证明所有并发或树化场景。

附录二：完整可运行源码

实测使用Amazon Corretto 17.0.12，运行时17.0.12+7-LTS，源码核对来自该安装目录的lib/src.zip。涉及内部方法与modCount的描述限定于这个实现；本篇实验不需要反射，也不修改JDK。

需要JDK17，下面文件命名为LinkedOrderLab.java，在新建目录执行：

javac -encoding UTF-8 LinkedOrderLab.java java LinkedOrderLab

程序打印运行时版本、每项PASS以及最后的检查总数；任何不符合预期的结果都会异常退出。无需第三方库，不连接数据库或网络。

本轮实际输出节选如下，省略了其余PASS行：

runtime=17.0.12+7-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_PASSED=24

我另外把淘汰条件故意改成size() >= limit，再运行同一套检查，程序在LRU after get(A)处报错，实际只剩B、C。因为插入第三条时就误删了A，之后get(A)无法把它移尾。这不是正确版本的输出，而是用来确认测试能抓住错误的失败对照。

import java.util.*; public class LinkedOrderLab { private static int checks; private static LinkedHashMap<String, Integer> sample(boolean access) { LinkedHashMap<String, 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, Map<String, Integer> map, String... keys) { List<String> actual = new ArrayList<>(map.keySet()); check(label + " " + actual, actual.equals(Arrays.asList(keys))); } static class Lru extends LinkedHashMap<String, 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.Entry<String, Integer> eldest) { return size() > limit; } } public static void main(String[] args) { System.out.println("runtime=" + System.getProperty("java.runtime.version")); LinkedHashMap<String, 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); LinkedHashMap<String, 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"); LinkedHashMap<String, Integer> iterated = sample(true); Iterator<String> 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")); LinkedHashMap<String, 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); } }