学习笔记08——ConcurrentHashMap实现原理及源码解析

1. 概述 为什么需要ConcurrentHashMap？

解决HashMap线程不安全问题：多线程put可能导致死循环（JDK7）、数据覆盖（JDK8）

优化HashTable性能：通过细粒度锁替代全局锁，提高并发度

对比表 特性HashMapHashTableConcurrentHashMap线程安全否是是锁粒度无锁全局锁分段锁/CAS+synchronized并发性能高极低高Null键/值允许不允许不允许 JDK版本差异

JDK7：基于Segment分段锁（默认16段）

JDK8+：数组+链表+红黑树，使用CAS + synchronized锁头节点

---

2. 线程安全实现机制 JDK8的锁优化 final V putVal(K key, V value, boolean onlyIfAbsent) {    // ...    for (Node<K,V>[] tab = table;;) {        Node<K,V> f; int n, i, fh;        if (tab == null || (n = tab.length) == 0)            tab = initTable();        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {            // CAS插入新节点（无锁）            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))                break;       }        else if ((fh = f.hash) == MOVED)            tab = helpTransfer(tab, f);        else {            synchronized (f) { // 锁住链表头节点                // 处理链表/红黑树插入           }       }   }    // ... }

CAS：用于无竞争情况下的快速插入（如空桶）

synchronized锁头节点：仅锁定当前哈希桶，不影响其他桶操作

---

3. 核心数据结构 Node节点结构 static class Node<K,V> implements Map.Entry<K,V> {    final int hash;    final K key;    volatile V val;    volatile Node<K,V> next;    // ... }

volatile修饰：保证可见性，确保读线程能立即看到更新

红黑树节点：TreeNode继承Node，用于处理长链表（阈值=8）

扩容机制

触发条件：元素数量超过sizeCtl

多线程协助：通过ForwardingNode标记正在迁移的桶，其他线程可参与迁移

---

4. 关键源码解析

以下是对 ConcurrentHashMap 核心源码的深度解读，结合 JDK8 的实现进行分析：

---

4.1核心方法源码解析 1. 初始化：initTable() private final Node<K,V>[] initTable() {    Node<K,V>[] tab; int sc;    while ((tab = table) == null || tab.length == 0) {        // sizeCtl < 0 表示其他线程正在初始化        if ((sc = sizeCtl) < 0)            Thread.yield(); // 让出 CPU，等待初始化完成        else if (U pareAndSwapInt(this, SIZECTL, sc, -1)) { // CAS 抢锁            try {                // 双重检查，防止重复初始化                if ((tab = table) == null || tab.length == 0) {                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                    table = tab = nt;                    sc = n - (n >>> 2); // 计算扩容阈值（0.75n）               }           } finally {                sizeCtl = sc; // 释放锁，设置阈值           }            break;       }   }    return tab; }

CAS 抢锁：通过 sizeCtl 标记初始化状态（-1 表示初始化中）。

双重检查：避免多线程重复初始化。

负载因子固定为 0.75：通过 sc = n - (n >>> 2) 实现。

---

2. put 方法：putVal() final V putVal(K key, V value, boolean onlyIfAbsent) {    if (key == null || value == null) throw new NullPointerException();    int hash = spread(key.hashCode()); // 计算哈希（高位参与运算）    int binCount = 0;    for (Node<K,V>[] tab = table;;) {        Node<K,V> f; int n, i, fh;        if (tab == null || (n = tab.length) == 0)            tab = initTable(); // 懒初始化        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 桶为空            if (casTabAt(tab, i, null, new Node<>(hash, key, value))) // CAS 插入                break;       } else if ((fh = f.hash) == MOVED) // 正在扩容            tab = helpTransfer(tab, f); // 协助扩容        else {            V oldVal = null;            synchronized (f) { // 锁住头节点                if (tabAt(tab, i) == f) { // 再次验证头节点未变                    if (fh >= 0) { // 链表节点                        binCount = 1;                        for (Node<K,V> e = f;; ++binCount) {                            K ek;                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {                                oldVal = e.val;                                if (!onlyIfAbsent)                                    e.val = value; // 更新值                                break;                           }                            Node<K,V> pred = e;                            if ((e = e.next) == null) {                                pred.next = new Node<>(hash, key, value); // 追加到链表尾部                                break;                           }                       }                   } else if (f instanceof TreeBin) { // 红黑树节点                        Node<K,V> p;                        binCount = 2;                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {                            oldVal = p.val;                            if (!onlyIfAbsent)                                p.val = value;                       }                   }               }           }            if (binCount != 0) {                if (binCount >= TREEIFY_THRESHOLD) // 链表长度 >=8                    treeifyBin(tab, i); // 可能树化                if (oldVal != null)                    return oldVal;                break;           }       }   }    addCount(1L, binCount); // 更新元素计数    return null; }

关键逻辑：

哈希计算：spread() 方法通过 (h ^ (h >>> 16)) & HASH_BITS 保证哈希值为正数。

CAS 插入空桶：若桶为空，直接通过 casTabAt 插入新节点（无锁优化）。

锁头节点处理冲突：对非空桶使用 synchronized 锁定头节点，处理链表或红黑树。

树化条件：链表长度 >=8 且数组长度 >=64 时树化，否则优先扩容。

并发扩容协作：若发现桶正在迁移（MOVED 标记），当前线程会协助迁移。

---

3. 扩容机制：transfer() private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {    int n = tab.length, stride;    // 计算每个线程处理的桶区间（最小 16）    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)        stride = MIN_TRANSFER_STRIDE;    if (nextTab == null) { // 初始化新数组        try {            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];            nextTab = nt;       } catch (Throwable ex) { sizeCtl = Integer.MAX_VALUE; return; }        nextTable = nextTab;        transferIndex = n; // 迁移起点为旧数组末尾   }    // 多线程协同迁移逻辑    ForwardingNode<K,V> fwd = new ForwardingNode<>(nextTab);    boolean advance = true;    boolean finishing = false;    for (int i = 0, bound = 0;;) {        Node<K,V> f; int fh;        while (advance) {            int nextIndex, nextBound;            if (--i >= bound || finishing)                advance = false;            else if ((nextIndex = transferIndex) <= 0) {                i = -1;                advance = false;           } else if (U pareAndSwapInt(this, TRANSFERINDEX, nextIndex,                      nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {                bound = nextBound;                i = nextIndex - 1;                advance = false;           }       }        // 实际迁移逻辑（略，处理链表/树拆分到新数组）   } }

核心设计：

多线程任务分配：通过 transferIndex 全局指针分配迁移区间（类似“工作窃取”）。

ForwardingNode 占位符：迁移中的桶会被标记为 ForwardingNode，读请求会转发到新数组。

链表拆分优化：根据哈希值的高位决定节点留在旧桶还是迁移到新桶（newIndex = oldIndex + oldCap）。

---

4. 无锁读：get() public V get(Object key) {    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;    int h = spread(key.hashCode());    if ((tab = table) != null && (n = tab.length) > 0 &&       (e = tabAt(tab, (n - 1) & h)) != null) {        if ((eh = e.hash) == h) {            if ((ek = e.key) == key || (ek != null && key.equals(ek)))                return e.val; // 命中头节点       } else if (eh < 0) // 特殊节点（红黑树或 ForwardingNode）            return (p = e.find(h, key)) != null ? p.val : null;        while ((e = e.next) != null) { // 遍历链表            if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))                return e.val;       }   }    return null; }

无锁保障：

tabAt() 使用 Unsafe.getObjectVolatile 保证读取最新内存值。

链表遍历期间依赖 volatile 修饰的 next 指针保证可见性。

遇到 ForwardingNode 时自动跳转到新数组查询。

---

4.2.关键优化总结 优化点实现方式锁粒度仅锁单个桶的头节点（JDK8），替代 JDK7 的分段锁CAS 无锁插入空桶通过 casTabAt 直接插入，避免锁竞争多线程协作扩容通过 ForwardingNode 和 transferIndex 分配任务区间计数优化使用 CounterCell[] 分散竞争，避免 size() 成为性能瓶颈红黑树退化机制当树节点 <=6 时退化为链表，避免频繁树化开销

---

4.3源码分析的思考题

为什么在链表长度超过 8 时可能选择扩容而不是直接树化？

数组较短时（<64），扩容能更有效减少哈希冲突。

如何保证扩容期间读操作的正确性？

通过 ForwardingNode 将读请求转发到新数组，写操作会等待迁移完成。

size() 方法为什么不是精确值？

高并发场景下精确统计代价过高，采用分片计数（CounterCell）近似值。

---

5. 并发操作分析

扩容期间读写协调

读操作：遇到ForwardingNode时转到新表查询

写操作：协助迁移当前桶后再执行插入

线程协作扩容 private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {    // 每个线程处理一个区间，完成后再领取新区间 }

通过stride步长划分任务区间

使用transferIndex指针协调多线程任务分配

---

6. 总结 设计亮点

锁分离：降低锁竞争概率

乐观锁优先：CAS无锁化尝试

粒度细化：从分段锁到桶级别锁

无锁读：volatile变量保证可见性

7.面试回答模板

面试官：请说一下ConcurrentHashMap的实现原理。 回答：

ConcurrentHashMap在JDK1.8中采用了数组+链表/红黑树的结构，通过CAS和synchronized实现高并发。

写操作：如果桶为空，用CAS插入头节点；否则锁住头节点处理链表或红黑树。

读操作：完全无锁，依赖volatile保证可见性。

扩容：多线程协作迁移数据，通过ForwardingNode标记已处理的桶。

线程安全：锁粒度细化到单个桶，结合CAS减少竞争。 对比HashTable，它的并发性能更高，且支持更高的并发度。

---

8.源码分析技巧

关注核心方法：putVal、get、transfer（扩容）、helpTransfer。

调试参数：通过-XX:+PrintConcurrentLocks观察锁竞争情况。

结合JMM：分析volatile变量（如table、sizeCtl）的内存可见性保证。

9.常见面试题

以下是关于 Java ConcurrentHashMap 的常见面试题及其详细解答，涵盖底层实现、线程安全机制、性能优化等核心内容：

---

1. ConcurrentHashMap 如何实现线程安全？

回答要点：

JDK7 的分段锁（Segment）： 将整个哈希表分成多个段（默认 16 段），每个段独立加锁，不同段的操作可以并发执行。

优点：降低锁粒度，减少竞争。

缺点：内存占用较高（每个段独立维护数组），并发度受段数限制。

JDK8 的 CAS + synchronized 锁优化：

CAS 无锁插入：当桶为空时，直接通过 CAS 插入新节点，避免加锁。

synchronized 锁头节点：当桶非空时，仅锁住链表或红黑树的头节点，锁粒度细化到单个桶。

扩容协作：多线程可以协同迁移数据，减少扩容时间。

---

2. ConcurrentHashMap 与 HashMap、HashTable 的区别？ 特性HashMapHashTableConcurrentHashMap线程安全非线程安全全局锁（方法级同步）CAS + 细粒度锁（桶级别）Null 键/值允许禁止禁止性能高（无锁）极低（全局锁）高（并发优化）迭代器一致性快速失败快速失败弱一致性实现机制数组+链表+红黑树数组+链表数组+链表+红黑树（JDK8+）

---

3. JDK7 和 JDK8 的 ConcurrentHashMap 实现差异？

JDK7：

基于 分段锁（Segment），每个段类似一个独立的哈希表。

默认 16 段，并发度固定，无法动态扩展。

内存占用较高（每个段维护独立的数组）。

JDK8：

抛弃分段锁，采用 CAS + synchronized 锁头节点，锁粒度细化到单个桶。

引入 红黑树，当链表长度 >=8 且数组长度 >=64 时树化，提升查询效率。

内存利用率更高（共享一个数组），并发度动态扩展。

支持 多线程协作扩容，迁移效率更高。

---

4. ConcurrentHashMap 的 put 方法流程？

计算哈希：spread(key.hashCode())（保证哈希值为正数）。

懒初始化：若数组为空，调用 initTable() 初始化。

定位桶：(n-1) & hash 计算桶下标。

CAS 插入空桶：若桶为空，直接通过 CAS 插入新节点。

处理哈希冲突：

若桶正在迁移（ForwardingNode），当前线程协助迁移。

非空桶锁住头节点，处理链表或红黑树的插入/更新。

树化检查：链表长度 >=8 时可能触发树化。

更新计数：调用 addCount() 更新元素总数（基于 CounterCell[] 分片计数）。

---

5. ConcurrentHashMap 的 size() 方法为什么不是完全精确的？

分片计数优化： 使用 CounterCell[] 数组分散计数更新，避免多线程竞争同一变量。

当无竞争时，直接更新 baseCount。

当检测到竞争时，使用 CounterCell 分片统计，最终结果为 baseCount + ∑CounterCell[i]。

设计权衡： 高并发场景下，精确统计需要全局锁，性能代价过高。size() 返回的是一个近似值，但实际开发中足够使用。

---

6. 如何保证 get() 操作的无锁和高性能？

volatile 变量： 桶数组和节点的 val、next 字段用 volatile 修饰，保证可见性。

无锁读设计：

tabAt() 使用 Unsafe.getObjectVolatile 直接读取内存最新值。

遍历链表或红黑树时不加锁，依赖 volatile 保证数据可见性。

扩容期间的读操作： 遇到 ForwardingNode 时，自动跳转到新数组查询数据。

---

7. ConcurrentHashMap 的扩容机制如何实现？

核心步骤：

触发条件：元素数量超过 sizeCtl（扩容阈值 = 0.75 * 数组长度）。

多线程协作：

首个线程创建新数组（长度翻倍），并分配迁移任务区间。

其他线程通过 transferIndex 领取迁移任务（步长 stride）。

迁移逻辑：

将旧数组的桶拆分为高低位链表，高位链表迁移到 旧下标 + 旧容量 的位置。

迁移完成的桶用 ForwardingNode 占位，表示已处理。

读写协调：

读操作：遇到 ForwardingNode 时跳转到新数组查询。

写操作：先协助迁移当前桶，再执行插入。

---

8. 链表何时会转为红黑树？何时会退化为链表？

树化条件：

链表长度 >=8（TREEIFY_THRESHOLD）。

数组长度 >=64（MIN_TREEIFY_CAPACITY），否则优先扩容。

退化条件：

红黑树节点数 <=6（UNTREEIFY_THRESHOLD）时退化为链表。

设计目的： 平衡查询效率和空间占用，避免极端情况下的性能问题。

---

9. ConcurrentHashMap 为什么不允许 Null 键或 Null 值？

歧义性问题： get(key) 返回 null 时，无法区分是键不存在还是键对应的值为 null。

线程安全风险： 若允许 null，可能因并发操作导致隐式的 NullPointerException（如 containsKey(key) 和 get(key) 之间的竞争）。

设计一致性： ConcurrentHashMap 的设计目标是为并发场景提供明确的语义，禁止 null 可减少不确定性。

---

10. ConcurrentHashMap 的迭代器是强一致性还是弱一致性？

弱一致性： 迭代器在遍历时不会锁定整个哈希表，可能反映部分已完成的更新操作。

迭代过程中可能看到新增、删除或修改的键值对，但不保证完全一致。

设计目的是避免迭代期间阻塞其他线程，提升并发性能。

对比其他集合： HashMap 的迭代器是快速失败的（fail-fast），而 ConcurrentHashMap 的迭代器是安全的（fail-safe）。

---

11. 为什么 JDK8 改用 synchronized 而不是 ReentrantLock？

锁粒度细化： synchronized 在 JDK6 后进行了大量优化（如偏向锁、轻量级锁），性能与 ReentrantLock 接近。

内存消耗： ReentrantLock 需要额外维护 AQS 队列，内存开销更大。

代码简洁性： synchronized 语法更简洁，无需手动释放锁，减少编码错误。

---

12. ConcurrentHashMap 是否完全线程安全？

基本操作线程安全： put、get、remove 等单操作是原子的，线程安全。

组合操作非原子：

if (!map.containsKey(key)) map.put(key, value); // 非原子操作

此类组合操作需使用 putIfAbsent() 或外部同步。

迭代器弱一致性： 迭代期间可能看到其他线程的修改，但不会抛出 ConcurrentModificationException。

---

13. 如何理解 sizeCtl 字段的作用？

sizeCtl 是一个控制状态变量，具体含义：

>0：表示下一次扩容的阈值（0.75 * 当前容量）。

=0：默认初始状态。

=-1：表示哈希表正在初始化。

<-1：表示正在扩容，高 16 位表示扩容标识戳，低 16 位表示参与扩容的线程数 +1。

---

14. ConcurrentHashMap 的应用场景？

高并发缓存：如缓存用户会话信息、商品库存等。

实时统计：如多线程计数（需结合 addCount() 机制）。

替代 HashTable：所有需要线程安全哈希表的场景，性能更优。

分布式计算：如 MapReduce 任务中的局部结果聚合。

---

15. 如何设计一个线程安全的哈希表？

锁粒度优化： 从全局锁 → 分段锁 → 桶级别锁，逐步减少竞争。

无锁化尝试： 优先使用 CAS 处理无竞争场景（如空桶插入）。

并发扩容协作： 允许多线程协同迁移数据，提升扩容效率。

数据结构优化： 引入红黑树平衡查询效率，动态退化避免空间浪费。