← 返回首页 📚 实战课程
📑 本篇章节导航 (共5章,点击直达)
本节目标(学完能回答的面试题)核心知识(1小时精讲内容)面试速记卡(考前30秒速看)练习题(自测)学习资料

L07 - ConcurrentHashMap源码

本节目标(学完能回答的面试题)

核心知识(1小时精讲内容)

一、JDK 7 vs JDK 8 对比


JDK 7:Segment分段锁
  ┌─────────────────────────────────────────────┐
  │  Segment[] (默认16段)                        │
  │  ┌──────────┐  ┌──────────┐                 │
  │  │Segment 0 │  │Segment 1 │ ...             │
  │  │ Reentrant│  │ Reentrant│                 │
  │  │  Lock    │  │  Lock    │                 │
  │  │ ┌──────┐ │  │ ┌──────┐ │                 │
  │  │ │HashEn│ │  │ │HashEn│ │                 │
  │  │ │try[] │ │  │ │try[] │ │                 │
  │  │ │ ↓↓↓  │ │  │ │ ↓↓↓  │ │                 │
  │  │ │链表   │ │  │ │链表   │ │                 │
  │  │ └──────┘ │  │ └──────┘ │                 │
  │  └──────────┘  └──────────┘                 │
  └─────────────────────────────────────────────┘
  并发度 = Segment数量(默认16,创建后不可变)

JDK 8:CAS + synchronized + 细粒度锁
  ┌─────────────────────────────────────────────┐
  │  Node[] table(和HashMap类似的结构)          │
  │  ┌─────┐                                     │
  │  │ [0] │ → null                              │
  │  ├─────┤                                     │
  │  │ [1] │ → Node → Node → ... (链表)          │
  │  ├─────┤                                     │
  │  │ [2] │ → TreeBin → TreeNode... (红黑树)    │
  │  ├─────┤                                     │
  │  │ [3] │ → ForwardingNode (迁移中标记)        │
  │  └─────┘                                     │
  │                                              │
  │  锁粒度:单个桶的头节点(synchronized)         │
  │  并发度 = 数组长度(可动态扩展)                │
  └─────────────────────────────────────────────┘
对比项JDK 7JDK 8
数据结构Segment[] + HashEntry[] + 链表Node[] + 链表 + 红黑树
锁机制Segment级别ReentrantLock桶级别CAS + synchronized
并发度固定(默认16)动态(=数组长度)
查询复杂度O(n)链表O(log n)红黑树
扩容各Segment独立扩容多线程协助扩容

二、核心常量与sizeCtl


// sizeCtl 的多种含义(非常重要!)
// -1    : 表正在初始化(只有一个线程能初始化)
// -(1 + nThreads) : 有n个线程正在参与扩容
// 0     : 表还没初始化
// > 0   : 下次扩容的阈值(capacity * loadFactor)

// 其他关键节点类型
static final int MOVED     = -1; // ForwardingNode(迁移中)
static final int TREEBIN   = -2; // TreeBin(红黑树根节点)
static final int RESERVED  = -3; // ReservationNode(computeIfAbsent占位)

三、putVal完整流程(核心源码)


final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode()); // 扰动函数
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;

        // ① 延迟初始化table
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();

        // ② 桶为空 → CAS插入(无锁!)
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }

        // ③ 桶头是ForwardingNode → 协助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);

        // ④ 桶不为空 → 加锁插入
        else {
            synchronized (f) { // 锁住桶头节点!
                if (tabAt(tab, i) == f) { // double-check
                    if (fh >= 0) {
                        // 链表处理
                        int binCount = 0;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                // key已存在,更新value
                                V oldVal = e.value;
                                if (!onlyIfAbsent || oldVal == null)
                                    e.value = value;
                                afterNodeAccess(e);
                                return oldVal;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                if (binCount >= TREEIFY_THRESHOLD - 1)
                                    treeifyBin(tab, hash);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 红黑树处理
                        Node<K,V> p;
                        int binCount = 0;
                        if ((p = ((TreeBin<K,V>)f).findTreeNode(hash, key, null)) != null) {
                            V oldVal = p.value;
                            if (!onlyIfAbsent || oldVal == null)
                                p.value = value;
                            afterNodeAccess(p);
                            return oldVal;
                        }
                        // 插入新节点到红黑树...
                    }
                }
            }
        }
        // ⑤ 检查是否需要扩容
        addCount(1L, binCount);
    }
    return null;
}

putVal流程图:


┌──────────────────────────────────────────────────────────────┐
│              ConcurrentHashMap.putVal                         │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  table未初始化? → initTable()(CAS自旋,只允许一个线程)      │
│                                                              │
│  桶为空? → casTabAt() 无锁CAS插入                           │
│     │成功 → break                                            │
│     │失败 → 自旋重试                                         │
│                                                              │
│  桶头hash==MOVED? → helpTransfer() 协助扩容                  │
│                                                              │
│  桶不为空 → synchronized(桶头节点) 加锁                       │
│     ├── double-check桶头是否变化                              │
│     ├── 链表:遍历查找/尾插                                   │
│     │   └── binCount≥8 → treeifyBin()                        │
│     └── 红黑树:TreeBin.findTreeNode/putTreeNode              │
│                                                              │
│  addCount(1, binCount) → 检查是否需要扩容                     │
│                                                              │
└──────────────────────────────────────────────────────────────┘

四、tabAt / casTabAt —— volatile读取与CAS


// 使用Unsafe进行volatile读取(保证可见性)
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

// CAS设置桶的节点
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                     Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

// 为什么不直接用 tab[i]?
// 因为Node数组元素本身不是volatile的(避免所有写都触发MESI协议)
// 而是通过Unsafe的getObjectVolatile/compareAndSwapObject
// 实现对单个桶的精确volatile读写

五、sizeCtl与initTable


private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // sizeCtl=-1,其他线程正在初始化,让出CPU
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            // CAS成功,获得初始化权
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_INITIAL_CAPACITY;
                    Node<K,V>[] nt = (Node<K,V>[])new Node[n];
                    table = tab = nt;
                    sc = n - (n >>> 2); // sc = 0.75 * n
                }
            } finally {
                sizeCtl = sc; // 设置扩容阈值
            }
            break;
        }
    }
    return tab;
}

六、多线程协助扩容(transfer)


扩容触发条件:元素总数 > sizeCtl(即 capacity * 0.75)

核心机制:多线程分段迁移

  原数组(长度=32):
  [0][1][2][3]...[15][16][17]...[31]

  线程A负责迁移:桶 0~7
  线程B负责迁移:桶 8~15
  线程C负责迁移:桶 16~23
  线程D负责迁移:桶 24~31

  迁移过程:
  1. 每个线程用CAS领取一段桶(默认每段16个桶:stride = NCPU > 1 ? (n >>> 3) / NCPU : n)
  2. 从后往前迁移每个桶
  3. 迁移完一个桶后,在该桶放入ForwardingNode(hash=MOVED)
  4. 其他线程put时发现桶是ForwardingNode → helpTransfer协助迁移
  5. 所有桶迁移完成后,切换到新数组

ForwardingNode:
  - hash = MOVED (-1)
  - 指向新数组 nextTable
  - get操作时:如果遇到ForwardingNode,到新数组中查找

// transfer 核心逻辑(简化)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 计算每个线程迁移的步长
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // 最小16

    // 第一个发起扩容的线程负责初始化nextTab
    if (nextTab == null) {
        Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1]; // 2倍
        nextTab = nt;
        nextTable = nt;
        transferIndex = n; // 从数组末尾开始分配
    }

    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);

    for (int i = 0, bound = 0;;) {
        // 领取迁移区间:CAS修改 transferIndex
        // bound = 本次的起始索引, i = 当前处理的索引
        // ...
        // 迁移桶 i(和HashMap一样的高低位拆分)
        // 迁移完成后 tab[i] = fwd (ForwardingNode)
    }
}

七、counterCell计数机制


// ConcurrentHashMap如何统计元素个数?
// 不能用单个AtomicLong(高并发下CAS竞争激烈)
// 参考 LongAdder 的思路:分散计数

// baseCount + CounterCell[]
//   无竞争时 CAS更新 baseCount
//   有竞争时(CAS失败)→ 使用CounterCell分散计数

private transient volatile CounterCell[] counterCells;
private transient volatile long baseCount;

// size() 方法:求和
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 : (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}

final long sumCount() {
    CounterCell[] as = counterCells;
    long sum = baseCount;
    if (as != null) {
        for (CounterCell a : as) {
            if (a != null)
                sum += a.value;
        }
    }
    return sum;
}

// addCount中的计数逻辑
private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 尝试CAS更新baseCount
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        // CAS失败 → 分散到CounterCell
        CounterCell a; long v; int m;
        // ... 在CounterCell[]中CAS更新某个Cell ...
    }
    // 检查是否需要扩容
    if (check >= 0) {
        // s = sumCount() > sizeCtl → 扩容
    }
}

counterCell结构图:


┌──────────────────────────────────────────┐
│           元素计数                         │
│                                          │
│  baseCount: 1000                         │
│                                          │
│  CounterCell[]:                          │
│  ┌───────┬───────┬───────┬───────┐       │
│  │ 200   │ 150   │ null  │ 300   │ ...   │
│  └───────┴───────┴───────┴───────┘       │
│                                          │
│  总数 = baseCount + Σ(counterCells)       │
│       = 1000 + 200 + 150 + 300 = 1650    │
│                                          │
│  分散计数减少CAS竞争                       │
└──────────────────────────────────────────┘

八、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)
            // hash<0 特殊节点处理
            // ForwardingNode → 到nextTable查找
            // TreeBin → 红黑树查找
            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;
}

// get全程无锁!
// Node的val和next都是volatile的,保证可见性
// 即使正在扩容,也能通过ForwardingNode找到正确的数据

九、面试追问与回答

Q1: ConcurrentHashMap的key/value能为null吗?

不能。如果get(key)返回null,无法区分是"key不存在"还是"value就是null"。HashMap可以通过containsKey判断,但ConcurrentHashMap在并发环境下containsKey和get之间数据可能变化。

Q2: ConcurrentHashMap的并发度是多少?

JDK 7:并发度=Segment数量(默认16)。JDK 8:并发度=数组长度(动态变化),理论上每个桶可以并行操作。

Q3: 为什么JDK 8用synchronized而不是ReentrantLock?

(1) JDK 6后synchronized经过锁升级优化,轻量级场景下性能不亚于ReentrantLock;(2) synchronized不需要手动unlock,不会忘记释放;(3) synchronized的锁升级(偏向→轻量→重量)更适合"读多写少、锁持有时间短"的场景;(4) 减少内存开销(每个桶如果用ReentrantLock,需要大量Lock对象)。

Q4: ConcurrentHashMap能完全替代Hashtable吗?

功能上可以。ConcurrentHashMap在性能、内存、并发度上全面优于Hashtable。Hashtable的每个方法都加synchronized(全表锁),性能极差。但如果需要"强一致性"遍历(如遍历时锁定整个表),ConcurrentHashMap不提供这种语义。

Q5: size()方法返回的是精确值吗?

不是精确值。由于counterCell分散计数,sumCount()时可能存在并发修改,结果可能不完全准确。这是一个"最终一致性"的设计:性能优先于精确性。

面试速记卡(考前30秒速看)

练习题(自测)

1. 画出JDK 8 ConcurrentHashMap的putVal完整流程图,标注CAS和synchronized的使用位置。

2. 解释sizeCtl在不同阶段的各种值及其含义(初始化前、初始化中、正常运行中、扩容中)。

3. 为什么get操作可以完全无锁?volatile修饰了哪些字段?

4. 描述transfer扩容时多线程协助迁移的机制:线程如何领取任务、如何标记已完成、put操作如何感知扩容。

5. 比较ConcurrentHashMap的counterCell计数和LongAdder的Cell计数,有什么异同?

学习资料