原来ConcurrentHashMap里有这么多知识点

引言

最近给公司整理面试题，想起了Java里鼎鼎大名的ConcurrentHashMap（以后简称CHM）。原本以为懂了扩容（$2^n$）、单节点加锁、冲突红黑树就行了，结果一搜资料，再对比一下源码，发现原来还是有很多以前没留心过的知识点。所以在这里好好总结一下。

知识点

CHM如何存储数据

1. Node[] table；
2. Node[] nextTable；仅扩容时使用
3. 数组中的每个元素称作bin，
4. 如果K的hash值有冲突，则通过拉链或红黑树方式解决冲突，即bin中只存储该链表的头节点，或红黑树的根节点。

什么时候初始化存储空间

1. 构造函数不初始化数组
2. 第一次插入数据时初始化（table==null || table.length == 0）

如何计算空间大小

1. table的长度是$2^n$
2. 构造函数根据用户的目标容量，计算出所需的数组长度。
   计算方法是：

private static final int tableSizeFor(int c) {
        int n = c - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
1
2
3
4
5
6
7
8
9

经过几次无符号右移，就可以将n以下的所有二进制位全变为1，再加1，就变成了2的幂。
因为table的最大长度为2<<<30，所以代码中最多右移这5次就够了。

LoadFactor的作用

LoadFactor在HashMap中会作为属性记录下来，用于扩容时计算容量上限。但在CHM中只在构造函数中用于计算初始table大小而已，并不会作为属性记录下来。

虽然没有明确使用loadfactor这样的属性，但是CHM中仍会使用类似的机制。做法是：

1. 每次扩容后，记录sizeCtl的值为table长度的0.75，即$n-=n>>>2$
2. 是否需要扩容，即比较目标容量是否大于sizeCtl

什么时候需要扩容

触发扩容检查的路径

1. put --> putVal --> addCount
2. putAll --> tryPresize

【注意】只有当putVal产生hash冲突时，才会触发扩容检查。

扩容的标准

size()是否大于sizeCtl。而sizeCtl的值在不扩容的时候是table长度的0.75。

sizeCtl的作用

记录扩容阈值

也就是说每次扩容后，sizeCtl设置为table容量的0.75，即$n-=n>>>2$。当CHM的元素数量超过该阈值时，即触发扩容。

控制扩容的并发

我们试从addCount触发扩容检查开始解释sizeCtl的作用

private final void addCount(long x, int check) {
   。。。
   s = sumCount();
 }	
 // 上面通过baseCount和counterCells算得CHM的size
 if (check >= 0) {
    Node<K,V>[] tab, nt; int n, sc;
    // 如果CHM中的Node数已经超过sizeCtl，意味着需要扩容
    while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
            (n = tab.length) < MAXIMUM_CAPACITY) {
         // 根据n的前导0的个数 + 1<<15，算得扩容戳（校验值）
         int rs = resizeStamp(n);
		 // 参考else：设置扩容时的sizeCtrl=(rs<<16) + 2
         if (sc < 0) {
             // sizeCtrl>>>16 != rs，表示sizeCtrl和rs已经不是同一个n算出的。也就是意味着上一次扩容已经结束
             // 
             if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                 sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                 transferIndex <= 0)
                 break;
             // 每增加一个扩容线程，sizeCtl + 1
             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                 transfer(tab, nt);
         }
         // 设置“触发”扩容时的sizeCtl
         else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                      (rs << RESIZE_STAMP_SHIFT) + 2))
             transfer(tab, null);
         s = sumCount();
     } // while
  } // if(check>0)
} // addCount
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

写入时如何保证线程安全

四个措施保证写入时的线程安全：

1. 如果table尚未初始化，通过CAS操作将sizeCtrl设为-1，只有设置成功才能初始化table。这里采用类似双检锁的模式，保证只有一个线程初始化table
2. 如果目标bin（table中的元素）为空，则通过CAS的方式，生成一个Node，并保存到目标bin
3. 如果有Hash冲突，则对bin加锁，然后通过拉链或树化方式解决冲突
4. 如果目标bin已经迁移了nextTable，则当前线程不再执行写入操作，而是转而用做迁移

读取时如何保证线程安全

读取的时候不需要加锁。主要是因为

• table本身是volatile的
• Node的val是volatile的

volatile元素总是到内存中获取最新的值。