理解Java7和8里面HashMap+ConcurrentHashMap的扩容策略

快来打我* 2022-03-08 01:26 104阅读 0赞

# 转载：[https://blog.csdn.net/u010454030/article/details/82458413][https_blog.csdn.net_u010454030_article_details_82458413] #

2018年09月06日 11:25:56 [葬月魔帝][Link 1] 阅读数：974

### 前言 ###

理解HashMap和ConcurrentHashMap的重点在于：

（1）理解HashMap的数据结构的设计和实现思路

（2）在（1）的基础上，理解ConcurrentHashMap的并发安全的设计和实现思路

前面的文章已经介绍过Map结构的底层实现，这里我们重点放在其扩容方法， 这里分别对JDK7和JDK8版本的HashMap+ConcurrentHashMap来分析：

### JDK7的HashMap扩容 ###

这个版本的HashMap数据结构还是数组+链表的方式，扩容方法如下：

1.  `void transfer(Entry[] newTable) {`
2.  `Entry[] src = table; //src引用了旧的Entry数组`
3.  `int newCapacity = newTable.length;`
4.  `for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组`
5.  `Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素`
6.  `if (e != null) {`
7.  `src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）`
8.  `do {`
9.  `Entry<K, V> next = e.next;`
10. `int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置`
11. `e.next = newTable[i]; //标记[1]`
12. `newTable[i] = e; //将元素放在数组上`
13. `e = next; //访问下一个Entry链上的元素`
14. `} while (e != null);`
15. `}`
16. `}`
17. `}`

上面的这段代码不并不难理解，对于扩容操作，底层实现都需要新生成一个数组，然后拷贝旧数组里面的每一个Node链表到新数组里面，这个方法在单线程下执行是没有任何问题的，但是在多线程下面却有很大问题，主要的问题在于基于头插法的数据迁移，会有几率造成链表倒置，从而引发链表闭链，导致程序死循环，并吃满CPU。据说已经有人给原来的[SUN公司][SUN]提过bug，但sun公司认为，这是开发者使用不当造成的，因为这个类本就不是线程安全的，你还偏在多线程下使用，这下好了吧，出了问题这能怪我咯？仔细想想，还有点道理。

### JDK7的ConcurrentHashMap扩容 ###

HashMap是线程不安全的，我们来看下线程安全的ConcurrentHashMap，在JDK7的时候，这种安全策略采用的是分段锁的机制，ConcurrentHashMap维护了一个Segment数组，Segment这个类继承了重入锁ReentrantLock，并且该类里面维护了一个 HashEntry<K,V>\[\] table数组，在写操作put，remove，扩容的时候，会对Segment加锁，所以仅仅影响这个Segment，不同的Segment还是可以并发的，所以解决了线程的安全问题，同时又采用了分段锁也提升了并发的效率。 ![image][]

下面看下其扩容的源码：

1.  `// 方法参数上的 node 是这次扩容后，需要添加到新的数组中的数据。`
2.  `private void rehash(HashEntry<K,V> node) {`
3.  `HashEntry<K,V>[] oldTable = table;`
4.  `int oldCapacity = oldTable.length;`
5.  `// 2 倍`
6.  `int newCapacity = oldCapacity << 1;`
7.  `threshold = (int)(newCapacity * loadFactor);`
8.  `// 创建新数组`
9.  `HashEntry<K,V>[] newTable =`
10. `(HashEntry<K,V>[]) new HashEntry[newCapacity];`
11. `// 新的掩码，如从 16 扩容到 32，那么 sizeMask 为 31，对应二进制 ‘000...00011111’`
12. `int sizeMask = newCapacity - 1;`
13.  
14. `// 遍历原数组，老套路，将原数组位置 i 处的链表拆分到 新数组位置 i 和 i+oldCap 两个位置`
15. `for (int i = 0; i < oldCapacity ; i++) {`
16. `// e 是链表的第一个元素`
17. `HashEntry<K,V> e = oldTable[i];`
18. `if (e != null) {`
19. `HashEntry<K,V> next = e.next;`
20. `// 计算应该放置在新数组中的位置，`
21. `// 假设原数组长度为 16，e 在 oldTable[3] 处，那么 idx 只可能是 3 或者是 3 + 16 = 19`
22. `int idx = e.hash & sizeMask;`
23. `if (next == null) // 该位置处只有一个元素，那比较好办`
24. `newTable[idx] = e;`
25. `else { // Reuse consecutive sequence at same slot`
26. `// e 是链表表头`
27. `HashEntry<K,V> lastRun = e;`
28. `// idx 是当前链表的头结点 e 的新位置`
29. `int lastIdx = idx;`
30.  
31. `// 下面这个 for 循环会找到一个 lastRun 节点，这个节点之后的所有元素是将要放到一起的`
32. `for (HashEntry<K,V> last = next;`
33. `last != null;`
34. `last = last.next) {`
35. `int k = last.hash & sizeMask;`
36. `if (k != lastIdx) {`
37. `lastIdx = k;`
38. `lastRun = last;`
39. `}`
40. `}`
41. `// 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置`
42. `newTable[lastIdx] = lastRun;`
43. `// 下面的操作是处理 lastRun 之前的节点，`
44. `// 这些节点可能分配在另一个链表中，也可能分配到上面的那个链表中`
45. `for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {`
46. `V v = p.value;`
47. `int h = p.hash;`
48. `int k = h & sizeMask;`
49. `HashEntry<K,V> n = newTable[k];`
50. `newTable[k] = new HashEntry<K,V>(h, p.key, v, n);`
51. `}`
52. `}`
53. `}`
54. `}`
55. `// 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部`
56. `int nodeIndex = node.hash & sizeMask; // add the new node`
57. `node.setNext(newTable[nodeIndex]);`
58. `newTable[nodeIndex] = node;`
59. `table = newTable;`
60. `}`

注意这里面的代码，外部已经加锁，所以这里面是安全的，我们看下具体的实现方式：先对数组的长度增加一倍，然后遍历原来的旧的table数组，把每一个数组元素也就是Node链表迁移到新的数组里面，最后迁移完毕之后，把新数组的引用直接替换旧的。此外这里这有一个小的细节优化，在迁移链表时用了两个for循环，第一个for的目的是为了，判断是否有迁移位置一样的元素并且位置还是相邻，根据HashMap的设计策略，首先table的大小必须是2的n次方，我们知道扩容后的每个链表的元素的位置，要么不变，要么是原table索引位置+原table的容量大小，举个例子假如现在有三个元素（3,5,7）要放入map里面，table的的容量是2，简单的假设元素位置=元素的值 % 2，得到如下结构：

1.  `[0]=null`
2.  `[1]=3->5->7`

现在将table的大小扩容成4，分布如下：

1.  `[0]=null`
2.  `[1]=5->7`
3.  `[2]=null`
4.  `[3]=3`

因为扩容必须是2的n次方，所以HashMap在put和get元素的时候直接取key的hashCode然后经过再次均衡后直接采用&位运算就能达到取模效果，这个不再细说，上面这个例子的目的是为了说明扩容后的数据分布策略，要么保留在原位置，要么会被均衡在旧的table位置，这里是1加上旧的table容量这是是2，所以是3。基于这个特点，第一个for循环，作的优化如下，假设我们现在用0表示原位置，1表示迁移到index+oldCap的位置，来代表元素：

1.  `[0]=null`
2.  `[1]=0->1->1->0->0->0->0`

第一个for循环的会记录lastRun，比如要迁移\[1\]的数据，经过这个循环之后，lastRun的位置会记录第三个0的位置，因为后面的数据都是0，代表他们要迁移到新的数组中同一个位置中，所以就可以把这个中间节点，直接插入到新的数组位置而后面附带的一串元素其实都不需要动。

接着第二个循环里面在此从第一个0的位置开始遍历到lastRun也就是第三个元素的位置就可以了，只循环处理前面的数据即可，这个循环里面根据位置0和1做不同的链表追加，后面的数据已经被优化的迁移走了，但最坏情况下可能后面一个也没优化，比如下面的结构：

1.  `[0]=null`
2.  `[1]=1->1->0->0->0->0->1->0`

这种情况，第一个for循环没多大作用，需要通过第二个for循环[从头开始][Link 2]遍历到尾部，按0和1分发迁移，这里面使用的是还是头插法的方式迁移，新迁移的数据是追加在链表的头部，但这里是线程安全的所以不会出现循环链表，导致死循环问题。迁移完成之后直接将最新的元素加入，最后将新的table替换旧的table即可。

### JDK8的HashMap扩容 ###

在JDK8里面，HashMap的底层数据结构已经变为数组+链表+红黑树的结构了，因为在hash冲突严重的情况下，链表的查询效率是O(n），所以JDK8做了优化对于单个链表的个数大于8的链表，会直接转为红黑树结构算是以空间换时间，这样以来查询的效率就变为O(logN)，图示如下：

![image][image 1]

我们看下其扩容代码：

1.  `final Node<K,V>[] resize() {`
2.  `Node<K,V>[] oldTab = table;`
3.  `int oldCap = (oldTab == null) ? 0 : oldTab.length;`
4.  `int oldThr = threshold;`
5.  `int newCap, newThr = 0;`
6.  `if (oldCap > 0) {`
7.  `if (oldCap >= MAXIMUM_CAPACITY) {`
8.  `threshold = Integer.MAX_VALUE;`
9.  `return oldTab;`
10. `}`
11. `else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&`
12. `oldCap >= DEFAULT_INITIAL_CAPACITY)`
13. `newThr = oldThr << 1; // double threshold`
14. `}`
15. `else if (oldThr > 0) // initial capacity was placed in threshold`
16. `newCap = oldThr;`
17. `else { // zero initial threshold signifies using defaults`
18. `newCap = DEFAULT_INITIAL_CAPACITY;`
19. `newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);`
20. `}`
21. `if (newThr == 0) {`
22. `float ft = (float)newCap * loadFactor;`
23. `newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?`
24. `(int)ft : Integer.MAX_VALUE);`
25. `}`
26. `threshold = newThr;`
27. `@SuppressWarnings({"rawtypes","unchecked"})`
28. `Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];`
29. `table = newTab;`
30. `if (oldTab != null) {`
31. `for (int j = 0; j < oldCap; ++j) {`
32. `Node<K,V> e;`
33. `if ((e = oldTab[j]) != null) {`
34. `oldTab[j] = null;`
35. `if (e.next == null)`
36. `newTab[e.hash & (newCap - 1)] = e;`
37. `else if (e instanceof TreeNode)`
38. `((TreeNode<K,V>)e).split(this, newTab, j, oldCap);`
39. `else {`
40. `//重点关注区域`
41. `// preserve order`
42. `Node<K,V> loHead = null, loTail = null;`
43. `Node<K,V> hiHead = null, hiTail = null;`
44. `Node<K,V> next;`
45. `do {`
46. `next = e.next;`
47. `if ((e.hash & oldCap) == 0) {`
48. `if (loTail == null)`
49. `loHead = e;`
50. `else`
51. `loTail.next = e;`
52. `loTail = e;`
53. `}`
54. `else {`
55. `if (hiTail == null)`
56. `hiHead = e;`
57. `else`
58. `hiTail.next = e;`
59. `hiTail = e;`
60. `}`
61. `} while ((e = next) != null);`
62. `if (loTail != null) {`
63. `loTail.next = null;`
64. `newTab[j] = loHead;`
65. `}`
66. `if (hiTail != null) {`
67. `hiTail.next = null;`
68. `newTab[j + oldCap] = hiHead;`
69. `}`
70. `}`
71. `}`
72. `}`
73. `}`
74. `return newTab;`
75. `}`
76.

在JDK8中，单纯的HashMap数据结构增加了红黑树是一个大的优化，此外根据上面的迁移扩容策略，我们发现JDK8里面HashMap没有采用头插法转移链表数据，而是保留了元素的顺序位置，新的代码里面采用：

1.  `//按原始链表顺序，过滤出来扩容后位置不变的元素（低位=0），放在一起`
2.  `Node<K,V> loHead = null, loTail = null;`
3.  `//按原始链表顺序，过滤出来扩容后位置改变到（index+oldCap）的元素（高位=0），放在一起`
4.  `Node<K,V> hiHead = null, hiTail = null;`

把要迁移的元素分类之后，最后在分别放到新数组对应的位置上：

1.  `//位置不变`
2.  `if (loTail != null) {`
3.  `loTail.next = null;`
4.  `newTab[j] = loHead;`
5.  `}`
6.  `//位置迁移(index+oldCap)`
7.  `if (hiTail != null) {`
8.  `hiTail.next = null;`
9.  `newTab[j + oldCap] = hiHead;`
10. `}`

JDK7里面是先判断table的存储元素的数量是否超过当前的threshold=table.length\*loadFactor（默认0.75），如果超过就先扩容，在JDK8里面是先插入数据，插入之后在判断下一次++size的大小是否会超过当前的阈值，如果超过就扩容。

### JDK8的ConcurrentHashMap扩容 ###

在JDK8中彻底抛弃了JDK7的分段锁的机制，新的版本主要使用了Unsafe类的CAS自旋赋值+synchronized同步+LockSupport阻塞等手段实现的高效并发，代码可读性稍差。

ConcurrentHashMap的JDK8与JDK7版本的并发实现相比，最大的区别在于JDK8的锁粒度更细，理想情况下talbe数组元素的大小就是其支持并发的最大个数，在JDK7里面最大并发个数就是Segment的个数，默认值是16，可以通过构造函数改变一经创建不可更改，这个值就是并发的粒度，每一个segment下面管理一个table数组，加锁的时候其实锁住的是整个segment，这样设计的好处在于数组的扩容是不会影响其他的segment的，简化了并发设计，不足之处在于并发的粒度稍粗，所以在JDK8里面，去掉了分段锁，将锁的级别控制在了更细粒度的table元素级别，也就是说只需要锁住这个链表的head节点，并不会影响其他的table元素的读写，好处在于并发的粒度更细，影响更小，从而并发效率更好，但不足之处在于并发扩容的时候，由于操作的table都是同一个，不像JDK7中分段控制，所以这里需要等扩容完之后，所有的读写操作才能进行，所以扩容的效率就成为了整个并发的一个瓶颈点，好在Doug lea大神对扩容做了优化，本来在一个线程扩容的时候，如果影响了其他线程的数据，那么其他的线程的读写操作都应该阻塞，但Doug lea说你们闲着也是闲着，不如来一起参与扩容任务，这样人多力量大，办完事你们该干啥干啥，别浪费时间，于是在JDK8的源码里面就引入了一个ForwardingNode类，在一个线程发起扩容的时候，就会改变sizeCtl这个值，其含义如下：

1.  `sizeCtl ：默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。`
2.  `-1 代表table正在初始化`
3.  `-N 表示有N-1个线程正在进行扩容操作`
4.  `其余情况：`
5.  `1、如果table未初始化，表示table需要初始化的大小。`
6.  `2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍`

扩容时候会判断这个值，如果超过阈值就要扩容，首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素f，初始化一个forwardNode实例fwd，如果f == null，则在table中的i位置放入fwd，否则采用头插法的方式把当前旧table数组的指定任务范围的数据给迁移到新的数组中，然后 给旧table原位置赋值fwd。直到遍历过所有的节点以后就完成了复制工作，把table指向nextTable，并更新sizeCtl为新数组大小的0.75倍 ，扩容完成。在此期间如果其他线程的有读写操作都会判断head节点是否为forwardNode节点，如果是就帮助扩容。

扩容源码如下：

1.  `private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {`
2.  `int n = tab.length, stride;`
3.  `if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)`
4.  `stride = MIN_TRANSFER_STRIDE; // subdivide range`
5.  `if (nextTab == null) { // initiating`
6.  `try {`
7.  `@SuppressWarnings("unchecked")`
8.  `Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];`
9.  `nextTab = nt;`
10. `} catch (Throwable ex) { // try to cope with OOME`
11. `sizeCtl = Integer.MAX_VALUE;`
12. `return;`
13. `}`
14. `nextTable = nextTab;`
15. `transferIndex = n;`
16. `}`
17. `int nextn = nextTab.length;`
18. `ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);`
19. `boolean advance = true;`
20. `boolean finishing = false; // to ensure sweep before committing nextTab`
21. `for (int i = 0, bound = 0;;) {`
22. `Node<K,V> f; int fh;`
23. `while (advance) {`
24. `int nextIndex, nextBound;`
25. `if (--i >= bound || finishing)`
26. `advance = false;`
27. `else if ((nextIndex = transferIndex) <= 0) {`
28. `i = -1;`
29. `advance = false;`
30. `}`
31. `else if (U.compareAndSwapInt`
32. `(this, TRANSFERINDEX, nextIndex,`
33. `nextBound = (nextIndex > stride ?`
34. `nextIndex - stride : 0))) {`
35. `bound = nextBound;`
36. `i = nextIndex - 1;`
37. `advance = false;`
38. `}`
39. `}`
40. `if (i < 0 || i >= n || i + n >= nextn) {`
41. `int sc;`
42. `if (finishing) {`
43. `nextTable = null;`
44. `table = nextTab;`
45. `sizeCtl = (n << 1) - (n >>> 1);`
46. `return;`
47. `}`
48. `if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {`
49. `if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)`
50. `return;`
51. `finishing = advance = true;`
52. `i = n; // recheck before commit`
53. `}`
54. `}`
55. `else if ((f = tabAt(tab, i)) == null)`
56. `advance = casTabAt(tab, i, null, fwd);`
57. `else if ((fh = f.hash) == MOVED)`
58. `advance = true; // already processed`
59. `else {`
60. `synchronized (f) {`
61. `if (tabAt(tab, i) == f) {`
62. `Node<K,V> ln, hn;`
63. `if (fh >= 0) {`
64. `int runBit = fh & n;`
65. `Node<K,V> lastRun = f;`
66. `for (Node<K,V> p = f.next; p != null; p = p.next) {`
67. `int b = p.hash & n;`
68. `if (b != runBit) {`
69. `runBit = b;`
70. `lastRun = p;`
71. `}`
72. `}`
73. `if (runBit == 0) {`
74. `ln = lastRun;`
75. `hn = null;`
76. `}`
77. `else {`
78. `hn = lastRun;`
79. `ln = null;`
80. `}`
81. `for (Node<K,V> p = f; p != lastRun; p = p.next) {`
82. `int ph = p.hash; K pk = p.key; V pv = p.val;`
83. `if ((ph & n) == 0)`
84. `ln = new Node<K,V>(ph, pk, pv, ln);`
85. `else`
86. `hn = new Node<K,V>(ph, pk, pv, hn);`
87. `}`
88. `setTabAt(nextTab, i, ln);`
89. `setTabAt(nextTab, i + n, hn);`
90. `setTabAt(tab, i, fwd);`
91. `advance = true;`
92. `}`
93. `else if (f instanceof TreeBin) {`
94. `TreeBin<K,V> t = (TreeBin<K,V>)f;`
95. `TreeNode<K,V> lo = null, loTail = null;`
96. `TreeNode<K,V> hi = null, hiTail = null;`
97. `int lc = 0, hc = 0;`
98. `for (Node<K,V> e = t.first; e != null; e = e.next) {`
99. `int h = e.hash;`
100. `TreeNode<K,V> p = new TreeNode<K,V>`
101. `(h, e.key, e.val, null, null);`
102. `if ((h & n) == 0) {`
103. `if ((p.prev = loTail) == null)`
104. `lo = p;`
105. `else`
106. `loTail.next = p;`
107. `loTail = p;`
108. `++lc;`
109. `}`
110. `else {`
111. `if ((p.prev = hiTail) == null)`
112. `hi = p;`
113. `else`
114. `hiTail.next = p;`
115. `hiTail = p;`
116. `++hc;`
117. `}`
118. `}`
119. `ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :`
120. `(hc != 0) ? new TreeBin<K,V>(lo) : t;`
121. `hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :`
122. `(lc != 0) ? new TreeBin<K,V>(hi) : t;`
123. `setTabAt(nextTab, i, ln);`
124. `setTabAt(nextTab, i + n, hn);`
125. `setTabAt(tab, i, fwd);`
126. `advance = true;`
127. `}`
128. `}`
129. `}`
130. `}`
131. `}`
132. `}`

### 在扩容时读写操作如何进行 ###

(1)对于get读操作，如果当前节点有数据，还没迁移完成，此时不影响读，能够正常进行。

如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时get线程会帮助扩容。

(2)对于put/remove写操作，如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时写线程会帮助扩容，如果扩容没有完成，当前链表的头节点会被锁住，所以写线程会被阻塞，直到扩容完成。

### 对于size和迭代器是弱一致性 ###

volatile修饰的数组引用是强可见的，但是其元素却不一定，所以，这导致size的根据sumCount的方法并不准确。

同理Iteritor的迭代器也一样，并不能准确反映最新的实际情况

### 总结 ###

本文主要了介绍了HashMap+ConcurrentHashMap的扩容策略，扩容的原理是新生成大于原来1倍大小的数组，然后拷贝旧数组数据到新的数组里面，在多线程情况下，这里面如果注意线程安全问题，在解决安全问题的同时，我们也要关注其效率，这才是并发容器类的最出色的地方。

[https_blog.csdn.net_u010454030_article_details_82458413]: https://blog.csdn.net/u010454030/article/details/82458413
[Link 1]: https://me.csdn.net/u010454030
[SUN]: https://www.baidu.com/s?wd=SUN%E5%85%AC%E5%8F%B8&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[image]: /images/20220308/87e4a51c1ce74b5e84fc346680b06523.png
[Link 2]: https://www.baidu.com/s?wd=%E4%BB%8E%E5%A4%B4%E5%BC%80%E5%A7%8B&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[image 1]: /images/20220308/1d260c46132a4f039c74669d8ed34d5e.png