分布式微服务系统架构第108集：ConcurrentHashMap，LinkedHashMap底层原理详解

加群联系作者vx：xiaoda0423

仓库地址：https://webvueblog.github.io/JavaPlusDoc/

https://1024bat.cn/

ConcurrentHashMap 底层原理详解

🚀 一、整体结构

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    
    transient volatile Node<K,V>[] table;
    ...
}

核心字段说明：

🧱 二、数据结构：数组 + 链表/红黑树 + CAS + 锁分段

📌 节点结构（类似 HashMap，但加了 volatile 和 final）

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

• val 和 next 都是 volatile，确保线程之间可见性。

• 头节点不可变。

📌 红黑树结构（桶中元素超过阈值时触发）

static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    boolean red;
}

🔒 三、并发控制机制

✅ 1. 分段锁机制（JDK 1.7）

• 使用 Segment[]，每段维护一把锁，适合读多写少。

• 每次锁的是 Segment 级别。

❌ JDK 1.8 移除了 Segment，用 CAS + synchronized + volatile 实现更细粒度的控制。

✅ 2. JDK 1.8 并发控制策略

🔄 四、核心方法底层原理

🧠 put(K,V)

public V put(K key, V value) {
    return putVal(key, value, false);
}

🌊 putVal(...) 核心步骤：

1. 初始化 table（CAS 保证只有一个线程执行）

2. 定位桶索引：(n - 1) & hash

3. CAS 尝试插入：如果桶为空，则用 CAS 插入

4. 桶非空时：加 synchronized 锁并：

• 遍历链表更新或追加

• 如果链表超过阈值（默认 8），转红黑树

• 桶插入完成后，检查是否需要扩容

• ---

  🧠 get(Object key)

  1. 计算哈希值定位桶

  2. 直接读取 Node（使用 volatile 保证可见性）

  3. 遍历链表或红黑树查找

  get 是无锁操作，非常高效。

  ---

  🔁 resize()

  1. table 长度翻倍

  2. 多线程并发迁移旧节点到新 table（通过 ForwardingNode 标记正在迁移）

  3. 使用 transferIndex 字段分批迁移，避免全表阻塞

  // ForwardingNode 表示该桶已经迁移过
  static final class ForwardingNode<K,V> extends Node<K,V> {
      final Node<K,V>[] nextTable;
  }

  ---

  📌 五、重要优化点

  ✅ CAS（Compare And Swap）

  • 用于 table 初始化、桶插入的无锁并发控制

  • 比如：table 初始化使用 UNSAFE.compareAndSwapObject

  ✅ synchronized（局部锁）

  • 仅用于桶中元素遍历时加锁，粒度极小

  ✅ volatile（可见性）

  • 所有关键共享变量（如 Node.val、Node.next、table 本身）都为 volatile，确保线程间可见性

  ---

  🧮 六、扩容机制

  触发条件	table 中元素个数超过 threshold
  执行方式	多线程协作，非阻塞迁移
  新旧表关系	使用 ForwardingNode 链接旧桶和新桶

  ---

  ✅ 总结表格：ConcurrentHashMap 和 HashMap 区别（JDK8）

  特性	HashMap	ConcurrentHashMap
  线程安全	❌	✅
  并发机制	无	CAS + synchronized
  扩容机制	单线程 resize	多线程协同 resize
  链表转树	✅（>8）	✅（>8）
  null 键值	key 和 value 都允许 null	都不允许 null
  读写性能	多线程低	多线程高

  ConcurrentHashMap 线程安全的核心原因在于它通过多种并发机制组合实现了高性能下的线程安全：

  ---

  ✅ 一句话总结：

  ConcurrentHashMap 利用 volatile + synchronized + CAS 等机制，实现了分段加锁、原子操作与可见性保障，从而在并发场景下保持线程安全。

  ---

  🔒 1. 分段锁机制（JDK 1.7）

  • JDK7 中 ConcurrentHashMap 采用 Segment 数组分段锁。

  • 每个 Segment 相当于一个小型 HashTable，每个 Segment 有一把独立的锁。

  • 多线程访问不同 Segment 时不会竞争，减少锁粒度。

  缺点：Segment 数组固定大小，扩展性差。

  ---

  🧠 2. JDK 1.8 改进点：彻底移除 Segment，核心变成：

  机制	用途
  CAS	表初始化、桶插入（无锁）
  volatile	table、val、next 等共享变量可见性
  synchronized	桶非空时加锁处理链表或树节点
  分段粒度操作	每次只锁桶头节点，不影响其它桶并发

  ---

  🔹 实例：put() 是如何线程安全的？

  public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
  }

  内部步骤：

  1. table 初始化：

  • 使用 CAS 保证只有一个线程成功初始化 table。

  • 多线程其他失败后重试。

• 定位桶索引：

• • index = (n - 1) & hash

• 桶为空：使用 CAS 插入新节点，无锁直接成功。

• 桶非空：加 synchronized 锁只锁当前桶头，处理链表/树。

• 扩容阶段：

• • 多线程协同搬迁桶（通过 ForwardingNode 标记迁移完成）

  ---

  👁️ 3. volatile 保证可见性

  • Node.val、Node.next、table 都是 volatile。

  • 保证一个线程写入后，其他线程读取立即可见。

  ---

  🧪 4. CAS（Compare-And-Swap）保证原子性

  • 主要用于：

  • • 初始化 table（只初始化一次）

    • 向空桶插入节点时的竞争（Node CAS）

    • 扩容索引迁移 transferIndex 的并发操作

  CAS 能避免加锁，提高并发性能。

  ---

  ✨ 5. 桶级锁（synchronized）粒度非常小

  只在如下情况使用锁：

  • 桶头非空，链表或树遍历插入或更新。

  • 树结构转换（链表节点多于 8）

  锁的粒度是桶级别，不会锁全表。

  ---

  ConcurrentHashMap 通过 细粒度桶锁、CAS 原子性、volatile 可见性 保证线程安全，同时保持了高并发性能。

  new LinkedHashMap<>();

  LinkedHashMap 是 Java 中一个非常好用的集合类，它结合了 HashMap 的高性能查找能力 和 List 的有序性

  为什么它好用？

  特性	原因 / 场景
  🔍 查找快	和 HashMap 一样，O(1) 时间复杂度，基于哈希定位。
  📚 顺序可控	默认按“插入顺序”遍历，非常适合：配置加载、事件码映射、缓存策略。
  🔄 可做 LRU 缓存	通过构造函数设置 accessOrder=true，可以实现 LRU（最近最少使用）缓存逻辑。
  🧠 可预测性强	相比 HashMap（遍历顺序不固定），它返回的数据顺序是可预测的，避免坑。