LinkedHashMap：插入顺序、访问顺序与 LRU

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 默认插入顺序与显式访问顺序分别讨论；LRU 的过期与并发策略另定。

解题路线

1. HashMap 桶提供按键定位，链式顺序结构提供确定遍历。默认保留插入次序，更新已有键通常不改插入位置。
2. 访问顺序模式下，相关访问把项移动到最近位置；因此 get 也会改变结构，需要纳入并发保护。
3. 容量 LRU 可在插入后淘汰最老项，但 TTL、权重容量、统计和异步加载需要附加设计，不能从 removeEldestEntry 推导全部能力。
4. 遍历与修改需遵守容器合同；包装同步 map 时，复合操作与遍历仍要正确持锁，慢 loader 不宜在全局锁里执行。

手动走一遍

插入 A/B/C，再访问 A，插入顺序仍 A/B/C；访问顺序变 B/C/A。容量3后插 D，LRU 淘汰 B。返回 value 不等于复制它，调用方仍可能修改内部可变对象。

规模与取舍

良好散列下查找和链移动平均 O(1)，遍历 O(n)，额外链指针占空间；缓存 miss 的外部加载成本另算。

易错点与追问

容易失分的边界

• get 永远只读。
• 默认就是 LRU。
• LRU 自动具备 TTL 和线程安全。

继续深挖

• TTL 与容量驱逐同时发生如何定义？
• 如何避免多个线程重复加载同一键？