ConcurrentHashMap源码分析 |
ConcurrentHashMap源码分析
1.7
存储结构
segment+HashEntry
初始化 ConcurrentHashMap无参构造
必要参数校验。
校验并发级别 concurrencyLevel 大小,如果大于最大值,重置为最大值。无惨构造默认值是 16.
寻找并发级别 concurrencyLevel 之上最近的 2 的幂次方值,作为初始化容量大小,默认是 16。
记录 segmentShift 偏移量,这个值为【容量 = 2 的N次方】中的 N,在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28.
记录 segmentMask,默认是 ssize - 1 = 16 -1 = 15.
初始化 segments[0]**,默认大小为 2,负载因子 0.75,扩容阀值是 2*0.75=1.5**,插入第二个值时才会进行扩容。
put
计算要 put 的 key 的位置,获取指定位置的 Segment
如果指定位置的 Segment 为空,则初始化这个 Segment
检查计算得到的位置的 Segment 是否为null
为 null 继续初始化,使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。
再次检查计算得到的指定位置的 Segment 是否为null.
用创建的 HashEntry 数组初始化这个 Segment.
自旋判断计算得到的指定位置的 Segment 是否为null,使用 CAS 在这个位置赋值为 Segment.
Segment.put 插入 key,value 值。
tryLock() 获取锁,获取不到使用 scanAndLockForPut 方法继续获取。
计算 put 的数据要放入的 index 位置,然后获取这个位置上的 HashEntry
遍历 put 新元素,为什么要遍历?因为这里获取的 HashEntry 可能是一个空元素,也可能是链表已存在,所以要区别对待。
如果这个位置上的 HashEntry 不存在
如果当前容量大于扩容阀值,小于最大容量,进行扩容。
直接头插法插入
如果这个位置上的 HashEntry 存在
判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
不一致,获取链表下一个节点,直到发现相同进行值替换,或者链表表里完毕没有相同的。
如果当前容量大于扩容阀值,小于最大容量,进行扩容。
直接链表头插法插入。
如果要插入的位置之前已经存在,替换后返回旧值,否则返回 null.
get
计算得到 key 的存放位置
遍历指定位置查找相同 key 的 value 值
refresh
只会扩容到原来的两倍
老数组里的数据移动到新的数组时,位置要么不变,要么变为 index+ oldSize
参数里的 node 会在扩容之后使用链表头插法插入到指定位置。
1.8
存储结构
数组+链表/红黑树
初始化initTable
通过自旋和 CAS 操作完成的
里面需要注意的是变量 sizeCtl ,它的值决定着当前的初始化状态。
-1 说明正在初始化
-N 说明有N-1个线程正在进行扩容
表示 table 初始化大小,如果 table 没有初始化
表示 table 容量,如果 table 已经初始化。
put
根据 key 计算出 hashcode
判断是否需要进行初始化
即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
如果都不满足,则利用 synchronized 锁写入数据
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树
get
根据 hash 值计算位置
查找到指定位置,如果头节点就是要找的,直接返回它的 value
如果头节点 hash 值小于 0 ,说明正在扩容或者是红黑树,查找之
如果是链表,遍历查找之