Wrap Up|JDK Map

LinkedHashMap

如何保证有序

LinkedHashMap 是 HashMap 的直接子类，底层数据结构中每一个 Node 在 Entry 的基础上又维护了两个指针： prev 和 next用于构建双向链表。在插入（或是get时）维护这个双向链表的指针，遍历时从 head 开始遍历以实现有序。

排序的维度

LinkedHashMap 排序的维度分为两种，由accessOrder 属性值决定，此属性可通过构造函数进行设置：

• 按插入顺序：默认，构造函数不指定或是指定 accessOrder = false；这种排序方式是在 put 操作后将对应节点放在链表的尾部。
• 按访问顺序：指定accessOrder = true；这种排序方式在 put 和 get 操作后都会将对应节点放在链表的尾部。

LRU缓存设计

基于 LinkedHashMap 的有序特性以及支持按照访问顺序对元素进行排序的模式，我们可以设计一个LRU缓存

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

核心重点：

1. 构造LRU实例时调用父类LinkedHashMap构造函数指定 accessOrder = true 以指定按访问顺序排序策略。由于按访问顺序排序的 LinkedHashMap 会将新 get 的元素放在链表尾部，因此在 LRU 缓存设计的视角来看：链表尾部的元素就是LRU的热点元素，链表头部的元素则是LRU的长时间未访问元素。
2. 重写 LinkedHashMap 默认留空的 removeEldestEntry，当当前元素数量超出指定容量后开启淘汰策略，淘汰链表头部（LRU的长时间未访问元素）

多线程环境使用问题

首先 LinkedHashMap 本身是非线程安全的，因此在多线程环境下，不能使用 LinkedHashMap

其次如果用的还是根据访问模式排序的策略，多线程 get 可能会出现难以排查和十分严重的问题：

1. 节点数据丢失 内存泄露
2. 链表成环 CPU 飙升
3. 上面说到的 ConcurrentModificationException

本质上是因为当 accessOrder = true 时，每次调用 get(key)，内部都会触发 afterNodeAccess(e) 方法。这个方法负责把当前节点移到双向链表的尾部，这个过程中每一步指针操作（before, after, head, tail）都不是原子的，也没有加锁，多线程环境下会出问题。

1）节点数据丢失

假设链表为：A <-> B <-> C。

• 线程 T1 执行 get(A)：试图把 A 移到 C 后面。
• 线程 T2 执行 get(B)：试图把 B 移到 C 后面。

并发过程：

1. T1 读取到尾节点 last = C。
2. T2 也读取到尾节点 last = C（注意：T2 不知道 T1 正在操作）。
3. T1 执行链接：C.after = A，并将 tail 更新为 A。
4. T2 执行链接：C.after = B，并将 tail 更新为 B。

后果： C.after 本来指向 A，瞬间被 T2 覆盖指向了 B。

• 结果：节点 A 虽然还在 HashMap 的哈希表中（可以通过 key 找到），但它从双向链表中“消失”了（断链）。
• 影响：当你遍历 Map 或使用 LRU 淘汰策略时，A 永远不会被遍历到，也永远不会被淘汰（导致内存泄漏）。

2）链表成环

在复杂的指针交换中，两个节点可能互相指向对方，形成闭环。

并发过程：

1. 线程 T1 准备把 A 移到末尾，正在修改 A.after。
2. 线程 T2 准备把 B 移到末尾，正在修改 B.before。
3. 如果时机凑巧，可能出现 A.next = B 且 B.next = A 的情况，或者 tail.next 指向了链表中间的某个节点。

后果： 当你调用 map.forEach()、map.values() 或者 ArrayList(map.values()) 进行遍历时，迭代器会沿着 next 指针无限跑下去。

• 现象：线上服务器 CPU 突然飙升到 100%，日志停止输出，程序假死。

3）ConcurrentModificationException

public static void main(String[] args) {
   LinkedHashMap<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
   map.put("k1", "v1");
   map.put("k2", "v2");
   map.put("k3", "v3");

   // 线程 T1：负责遍历（迭代器对 modCount 敏感）
   new Thread(() -> {
      // 这里的 forEach 本质上使用了迭代器
      try {
         map.forEach((k, v) -> {
            System.out.println("遍历: " + k);
            //保证T2线程能在下一次T1执行前先get
            try { Thread.sleep(50); } catch (Exception e) {}  
         });
      } catch (ConcurrentModificationException e) {
         System.err.println("捕获到并发修改异常！因为 get 操作修改了 modCount");
      }
   }).start();

   // 线程 T2：负责 get (在 accessOrder=true 时，这等同于写操作)
   new Thread(() -> {
      try { Thread.sleep(10); } catch (Exception e) {}
      System.out.println("执行 get 操作...");
      map.get("k1"); // 修改了链表结构，modCount++
   }).start();
}

并发过程：

1. 线程 T1 正在遍历 Map（比如做数据统计）。
2. 线程 T2 执行了一次 map.get(key)。

后果：

• LinkedHashMap 在 get() 时修改了链表结构，导致内部的 modCount++。
• 线程 T1 的迭代器在下一次 next() 时，检测到 modCount != expectedModCount，抛出 **ConcurrentModificationException**。