concurrentHashMap 1.8 核心原理详解

concurrentHashMap 的底层实现数据结构 为 数组 + 链表 （红黑树） 当链表长度大于 8时会触发 链表转红黑树，但如果 数组长度小于 64时是通过扩容 将 数据进行再散列，降低链表长度来降低 1.8 的插入和查询效率低，JDK1.8 采用的是尾插法(每次都要遍历整个链表)进行数据插入的，所以插入和查询效率当 链表长度小于等于8时，链表的效率是要高于红黑树O(log(n))时间复杂度的

（1）. 并发扩容 table 迁移数据并发

创建新数组为旧数组长度的 2 倍 n = oldTable.length << 1

* | --->  ThreadA    <----||--->      ThreadB     <----|
* ------------------------------------------------------
* | 0 | 1 | 2 | .... | 15 | 16 | 17 | ...... | 30 | 31 |
* ------------------------------------------------------

* ThreadB 将 16~31 数据进行迁移
* ------------------------------------------------------
* | 0 | 1 | 2 | .... | 31 | 32 | 33 | ...... | 62 | 63 |
* ------------------------------------------------------

数组从后向前按步长进行分配，迁移的数组元素 transferIndex = oldTable.length = 32;

第一轮： transferIndex 转移的索引为

transferIndex = 32

nextIndex = transferIndex = 32

nextBound = 16 CAS(操作替换 transferIndex)

= nextIndex > stride ? nextIndex - stride : 0

transferIndex = 16 （cas 替换）

bound = nextBound = 16

i = nextIndex -1 = 31

advance = false

跳出 while 循环 进行 synchronized (f) 加锁进行数据的转移

lastRun 的实现(遍历链表 将最后几个连续被散列到新数组的同一个桶位的元素 ln =0 newTable的低位区， hn 高位区 （i + n）)

红黑树 （TreeBin extends Node 内部隐藏了一个双向链表，迁移的也是对链表的操作，如果链表长度小于6的话会进行将树拆分成两个链表）

第二轮：

transferIndex = 16

nextIndex = 16

nextBound = nextIndex > stride ? nextIndex - stride : 0 (16 > 16 ？ 16 -16 : 0)

= 0

transferIndex = (CAS() 比较并交换后 等于 0)

bound = nextBound = 0

i = nextIndex - 1 = 15

advance = fase;

跳出while 迁移 table[0] ~ table[15] 之间的数据，ThreadB 能够 通过CAS 竞争到

addCount(1, binCount):

ConterCells ConcurrentHashMap 的数据元素的统计，当有多个线程同时 put () addCount()

* -----------------
* | 0 | 1 | 2 | 3 |
* -----------------
当多个线程 通过 计算得到的索引位存在竞争时，CAS(保证原子性) 获得执行的线程会将 cellBusy 设置成 -1， 
并且 将CounterCell 的 value + 1 ,另外的线程竞争失败会重新生成 hash 在散列，如果过扔有竞争，会对 
CounterCells 数组进行扩容来提高并发的执行效率  
* 
* ------------------------
* | 0 | 1 | .... | 6 | 7 |
* ------------------------