LinkedHashMap 在 Java 1.4 中被引入，作为一种混合数据结构，结合了 HashMap 的 O(1) 平均查找性能和提供确定性迭代顺序的双向链表，可以是插入顺序或访问顺序。其设计引入了 removeEldestEntry 模板方法，使子类能够通过在映射超过所需大小时返回 true 来实现 LRU（最近最少使用）驱逐策略。但是，该实现从未打算用于并发使用；它继承了 HashMap 的非线程安全特性，并增加了在所有条目之间维护双向 before 和 after 指针的复杂性，包括那些在树形桶内的条目。
在并发结构修改下——例如，一个线程插入而另一个线程删除或调整大小——链表指针可能非原子性地更新，导致图形结构损坏，其中条目形成循环引用或与主链断开。例如，如果线程 A 将条目的 after 指针更新为指向条目 B，但线程 B 同时删除条目 B 并更新其 before 指针，则列表可能以 A 指向 B，而 B 指向 C 的方式结束，有效地跳过 A 或创建一个循环。此类腐败导致迭代器无限旋转（消耗 100% CPU）或静默跳过有效条目，从而使 removeEldestEntry 策略变得不可靠，因为 "eldest" 指针可能不再反映列表的真实头部。
要安全地在多线程上下文中使用 LinkedHashMap，必须对所有操作进行外部同步。对于 accessOrder=true 的缓存，即使是 get() 也是一项结构修改（它重新排序了链表），因此标准的 ReadWriteLock 优化对于只读操作也是无效的；必须将所有操作视为写入，或使用全局互斥锁。最安全的方法是 Collections.synchronizedMap，尽管在迭代时您必须手动同步映射。但是，在生产系统中，建议用 Caffeine 或 Guava 的 CacheBuilder 替换 LinkedHashMap，这两者提供了不带全局争用的锁条纹或完全并发的驱逐算法。
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap 不是线程安全的；外部同步 this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // 所有方法必须在 map 上同步 public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // 迭代需要显式同步 public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
一个电子商务平台的后端服务需要一个内存缓存来存储产品定价数据，以减少数据库负载。最初的实现使用了 LinkedHashMap，并设置 accessOrder=true，重写了 removeEldestEntry 来强制限制在 1,000 个项目，假设映射会自动删除旧条目。在低负载测试期间，这项工作正常；然而，在四十个并发线程处理闪购时，该服务经历了间歇性的 CPU 峰值达到 100% 和最终的线程饥饿。
线程转储显示多个线程卡在 LinkedHashMap 迭代器内，遍历因并发修改而导致的双向链表中的循环引用。具体而言，一个线程在调整内部表的大小，而另一个线程在更新条目的访问顺序，导致一个 Entry 节点的 after 指针引用自身，在迭代期间创建了无限循环。此外，由于 "eldest" 指针因并发重新排序而被损坏，removeEldestEntry 回调偶尔会删除错误的条目，导致缓存翻转，其中最近访问的项目被驱逐，而不是陈旧的项目。
团队首先考虑使用 Collections.synchronizedMap 来包装该映射。优点：这需要最少的代码更改，并通过将它们包装在 synchronized 方法中确保单个操作的原子性。缺点：这引入了全局监视器，串行化所有读取和写入，导致吞吐量从预期的每秒 20,000 次操作降至在争用条件下的 3,000 次。此外，迭代器仍然需要显式的 synchronized(map) 块，开发者有时会忘记，导致 ConcurrentModificationException。
接下来，他们评估了将 ConcurrentHashMap 与 ConcurrentLinkedQueue 配对使用，以跟踪最近性和后台清理线程。优点：这提供了高并发的读取和写入。缺点：正确实现 LRU 是错误多发的；移除最老的条目与插入并不是原子性的，允许缓存在高负载下暂时显著超出其大小限制。此外，在每次 get() 时更新队列需要写操作，创造了类似的争用点，并在队列与映射之间维护一致性方面增加了复杂性。
最后，他们对 Caffeine 进行了基准测试，这是一种高性能缓存库。优点：它使用带有锁条纹的 BoundedLocalCache 和一个用于驱逐的写缓冲区，允许在不加锁的情况下进行并发读取和高吞吐量写入。它以原子的方式处理 LRU/W-TinyLFU 驱逐，而无需显式同步。缺点：它增加了外部依赖，并需要学习新的 API（例如，CacheLoader）。
经过负载测试后，他们选择了 Caffeine，因为它在 80,000+ 次操作每秒的情况下，99% 的延迟低于 1 毫秒；而同步的 LinkedHashMap 在 5k ops/sec 下瓶颈，99% 峰值达到 500 毫秒。迁移涉及将映射替换为 Caffeine.newBuilder().maximumSize(1000).build()，并注册一个移除监听器以实现清理逻辑。
部署后的监测显示 CPU 使用稳定，并且没有线程挂起。缓存命中率从 85% 提高到 94%，因为驱逐变得可预测且没有竞态条件。这一事件突显出 LinkedHashMap 是一种不适合并发 LRU 缓存的单线程数据结构，尽管它有便利的 API。
当条目因高哈希冲突而移动到树形桶（红黑树）中时，LinkedHashMap 如何维护条目的 LRU 顺序？
LinkedHashMap 使用一个专门的内部类 Entry，它扩展了 HashMap.Node，并包含 before 和 after 指针。当一个桶树形化时，LinkedHashMap 重写 newTreeNode 来创建仍然继承自 LinkedHashMap.Entry 的 TreeNode 实例（通过 LinkedHashMap.TreeNode）。因此，即使条目被存储在树形结构中以解决 O(log n) 的碰撞，它们仍然是全局双向链表中的节点。afterNodeAccess 方法在每次访问后更新这些指针，确保 LRU 链能够遍历条目，无论它们是在链表中还是在哈希表中的树中。
为什么在迭代期间对具有 accessOrder=true 的 LinkedHashMap 调用 get() 会触发 ConcurrentModificationException，而在标准 HashMap 上执行相同操作则不会？
在 accessOrder 模式下，LinkedHashMap 将 get() 视为结构修改，因为它将被访问的条目移动到双向链表的尾部，从而递增 modCount。快速失败的迭代器检查此计数器，并在检测到更改时立即抛出异常。相比之下，标准 HashMap 仅在插入、删除和调整大小时递增 modCount；get() 对于表结构来说是只读的。这一区别意味着即使是 "只读" 逻辑操作也可能使 LinkedHashMap 中的迭代器失效，因此在并发迭代时必须对所有操作（包括读取）进行同步。
在 LinkedHashMap 中，在哪种特定指针腐败发生在并发调整大小（重新哈希）期间，这是在标准 HashMap 中不可能出现的？
在调整大小期间，HashMap 将节点转移到新的表数组，如果是并发执行则可能导致桶中的无限循环。LinkedHashMap 还额外面临 before 和 after 指针的损坏，这些指针构成了辅助的链表。如果线程 A 正在重新连接条目以保留新表中的顺序，而线程 B 修改了列表（例如，通过 remove），则线程 A 可能将条目链接到线程 B 已经取消链接的后继，造成悬空引用或循环。具体来说，头节点的 after 指针可能指向的条目，其 before 指针被另一个线程置为 null，从而破坏列表不变性，并导致迭代器在调用 next() 时沿着损坏链永远旋转。