前言
正文
jdk版本:1.8.0_181
数据结构
数组,链表 红黑树;数据结构和HashMap
数据结构一样;
构造方法
1 |
|
常用的构造方法主要就是上面两种;
第一种:什么都没做,所以会使用默认的配置,默认配置就是数组长度为16
第二种:指定容器数组长度,这里和HashMap
的指定容器长度的构造方法差不多,都是调用了tableSizeFor
方法,
不同的是HashMap
直接将传入的值作为参数去调用tableSizeFor
方法,而ConcurrentHashMap
将传入的值进行了
initialCapacity + (initialCapacity >>> 1) + 1
,也就是在原来的基础上大概增加了一半
添加方法
提供对外调用的添加方法
1 |
|
第一个put
方法,这个方法是最常用的;
第二个是将Map
中的数据添加进ConcurrentHashMap
,实际使用for
循环Map
,再put
;
第三个也是添加,但是是在没有key
值的情况下才会添加;这种适合设置默认值的时候用;
上面三个方法都调用了putVal
方法:
1 |
|
说明:
synchronized
锁住部分代码与HashMap
基本差不多;但是处理流程和HashMap
就不同了;- 使用
cas
与synchronized
(这里是分段锁)来保证线程安全; - 扩容在
addCount
方法中,这里需要注意binCount
数值,在addCount
方法中会用到; - 上面这段代码中的
MOVED
状态,需要结合transfer
方法来观察;
流程:
- 判断是否初始化
- 判断是否为第一个节点
- 判断是否扩容
- 添加进桶中 4.1 锁住 4.1.1 判断链表 4.1.1.1 判断是末尾添加还是覆盖 4.1.2 判断是否红黑树 4.1.2.1 红黑树添加 4.2 判断桶中元素数量 4.2.1 判断是否将链表转红黑树 4.2.2 判断是添加还是覆盖,添加继续执行,覆盖则返回
- 添加数量(
addCount
)
初始化方法
1 |
|
初始化也使用了cas
来保证线程安全;也使用了双重校验数组长度是否为空;
还需要注意的是sizeCtl
,当容器正在扩容时,sizeCtl
是负数;
多线程竞争时,使用了Thread.yield()
;
添加容器元素数量
1 |
|
这个方法主要是两个功能:
一是修改容器元素数量值,也就是cas
修改baseCount
,但是这里需要注意的是,如果没有cas成功,则表示多线程竞争添加,就会分段cas,这里就不细说了;
二是判断是否需要扩容,也就是调用transfer
扩容;若正在扩容,则加速扩容;
总结起来就是:cas
,分段cas
;扩容,加速扩容
扩容
ConcurrentHashMap
的扩容是新建一个新的数组,容量是原来数组的两倍,然后再将原数组中元素添加到新建的数组中;
1 |
|
扩容的代码有点多,就不详细描述了:
- 扩容是新建一个新的数组,将原数组元素放进新数组中,流程大概和
HashMap
的扩容差不多; - 使用
cas
将ForwardingNode
放入原数组对应的节点中,标志已经移动;具体看fwd
元素的使用地方; - 关于
synchronized
代码块,具体可以先看HashMap
的扩容,两者是差不多的,这里就不细说了;
扩展
这个方法还有一点就是while
代码块,这个地方就是实现加速扩容的地方;下面具体说:
1 |
|
这个地方主要是进行i值计算,也就是数组(桶)的下标;
通过(transferIndex-stride)
来将原数组分段;多线程的情况下通过cas
来保证线程安全;
涉及参数:
transferIndex
:转移元素的索引;就是看转移数据转移到什么位置了;
stride
:每次转移的数量,这个值是根据CPU来计算的,最小值是16;
也就是当数组长度大于16时,才会分段加速;
获取方法
1 |
|
获取方法其实不难,注意点就是判断是否扩容那一步,这个find
方法是在ForwardingNode
类中;而不是Node
类中的;
其他方法
remove方法
1 |
|
上面两个方法都调用了replaceNode
方法;
1 |
|
sumCount方法
这个方法是对容器中的元素进行计算;
这里主要是想说明分段cas添加的数据是保存在counterCells中的;这个情况主要发生在多线程添加冲突的情况下
1 |
|