知识点

问：ConcurrentHashMap的长度可以是2的n次方以外的长度吗？怎么转成2的n次方长度？
答：不能，长度必须是2的n次方的长度，当设置的长度不是2的n次方长度时会进行转换，转换源码如下：

image.png
说明：>>>代表无符号又移动和>>的区别为，>>>忽略符号位，空位都以0补齐，>>保留符号位右移
如二进制1000 1001>>>2为0010 0010,1000 1001>>2为1000 0010
所以，n |= n >>> 1确保已经有两位是1了， 所以后面就可以移动两位再次运算类推，n |= n >>> 2确保四位是1...，最后加1就会成为2的n次方
注意：
负数的二进制在计算机中通过补码来表示，-1在计算机中表示为：1111 1111 ...1111（32个1），所以当c=0时，经过上面的运算n会为-1

问：ConcurrentHashMap是怎么更新数量的？
答：ConcurrentHashMap中有个baseCount的值，在更新数量的时候会通过CAS将baseCount加一，当失败的时候会通过线程计算随机值选择CounterCell[]中的位置将对应的CounterCell的值加一，在统计数量的时候除了统计baseCount的值，同时需要统计CounterCell[]数组中的值的总和。
（为什么这么设计？当只有baseCount的时候并发度为一，同时只有一个线程可以去改baseCount的值，加上CounterCell的相当于增加了并发度，性能更好）

问：ConcurrentHashMap是如何扩容的？
答：首先了解HashMap扩容时是扩容两倍，数组中的链表的元素扩容后的位置只会在当前位置或者，当前位置+n的位置（和hash算法有关，通过与数组长度进行与来获取hash值，所以当扩容长度*2时，hash值只会不变或者变一位，变一位及当前位置+n），之后进行遍历重新放入位置。
ConcurrentHashMap是并发访问的所以，在HashMap的基础上增加了多线程协助扩容的策略，每个线程分配几个桶进行扩容。为了保证多个线程之间不会分配到同一个桶，会有一个transferIndex的变量，扩容时transferIndex=table.length通过cas改变其位置来得到当前线程需要扩容桶（最少为16个），为了保证在当前位置扩容的时候没有新的数据put进来，扩容该节点时会将table上的该节点进行上锁，为了保证当前节点扩容完成后该节点的数据也不会有新加，节点扩容完成后会将原来table中的位置设置成ForwardingNode，代表正在扩容，其他线程识别到后会协助进行扩容。
线程协助扩容的地方有两个，一个是put的时候计算所在table中的节点的hash值为-1直接进行扩容，或者在插入数据更新数量后判断sizeCtl是否正在扩容态，如果是则帮助扩容
属性说明：
table属性
hash桶的记录是个数组

sizeCtl属性
记录table的状态

sizeCtl>0
初始化容量
扩容的阈值，0.75n
sizeCtl=-1表示正在初始化
sizeCtl<0表示正在扩容
sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 :表示此时只有一个线程在执行扩容

nextTable属性
暂存扩容后的table，扩容完成后会将table设置为nextTable

transferIndex属性
扩容到桶的位置的属性，扩容时默认为table的数组长度

stride属性
每个线程负责扩容的桶的长度

ForwardingNode属性
扩容时的临时节点，继承于Node，key和value都为null，hash为MOVE，同时会存储nextTable

扩容的时候有查找请求怎么找？
答：首先根据key算出hash，找到所在table中的位置，如果位置的hash值为不为-1正常的查找，遍历链表进行比对，如果hash值为-1（ForwardingNode）代表正在扩容，且当前节点已经扩容完成，这时会通过ForwardingNode的find方法去找，ForwardingNode中会存nextTable的引用，通过nextTable进行查找

扩容时sizeCtl值说明：

image.png
image.png

Integer.numberOfLeadingZeros方法的作用是计算整数二进制第一位为1的前面有多少个0，如整数2，返回结果为30（整数32位），RESIZE_STAMP_BITS的值为16，确保resizeStamp返回的结果左移16位后值为负数，同时左移16位后，前16位可以记录正在扩容的状态，后16位来记录当前协助扩容线程的数量

备注

• ConcurrentHashMap不支持key和value为null
• ConcurrentHashMap和HashMap以及List的初始化都是懒加载，只有在使用的时候才会去初始化数组

待解决问题

在操作ConcurrentHashMap的时候线程挂掉，是不是可能导致问题？如：插入元素后线程挂掉没有更新数量，导致数量与实际元素不匹配，在扩容过程中线程帮助扩容分配到桶，此时线程挂掉是不是就会丢数据。