- 初始化
- Segment个数
- HashEntry个数
- put()方法
- get()方法
- size()方法
- 扩容resize()方法
初始化主要区别:
1.7 采用的是分段加锁, Segment(区段) + HashEntry + Unsafe
1.8 撇弃了Segment, 锁的粒度细化到具体每个桶上的头结点, 并加上CAS和Synchronize加锁
— jdk1.7 —
jdk1.7的ConcurrenHashMap结构如图:
-
采用了Segment分段, 每个Segment里面有table数组, 数组放的是HashEntry, 所以每个Segment都相当于一个小HashMap
-
所以如果要定位一个元素, 需要用hash值进行2次定位, 第一次找到Segment, 第二次找到Entry.
-
Segment继承了ReentrantLock, 所以具备加锁的能力
取自于concurrencyLevel这个变量.表示并发级别, 注释说的是
the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads
估计的并发更新线程数。实现执行内部大小调整以尝试容纳这么多线程
如果未自定义,默认是这个常量DEFAULT_CONCURRENCY_LEVEL=16,
它的最大值是2的16次方, 即65536
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
...
Segment[] ss = (Segment[])new Segment[ssize];
根据上面的代码可知, Segment的大小根据并发级别来定, 并且一定是二次幂，Segment的大小最多65536个
HashEntry个数HashEntry的最小值, 有个常量MIN_SEGMENT_TABLE_CAPACITY=2 , 所以每个Segment最少有2个Entry
int c = initialCapacity / ssize; //默认的话分别是16 / 16
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY; //默认是2
while (cap < c)
cap <<= 1; //同样是确保2次幂
...
Segment s0 =
new Segment(loadFactor, (int)(cap * loadFactor),
(HashEntry[])new HashEntry[cap]);
— jdk1.8 —
类似于HashMap一样, 都是懒加载. 创建的时候是个空table, 第一次put的时候才会初始化容量为16的table
— jdk1.7 —
- 因为Segment区段和HashEntry的关系, 所以需要用hash值两次定位存储位置
- 根据hash得到目标segment位置, 如果segment为null, 使用CAS初始化后返回
- 然后根据segment继承ReentrantLock的自带锁的特性, 对其自旋tryLock尝试加锁. 在自旋的时候也没闲着, 它会去检查这个桶的头结点是否为空, 找不到就创建一个新Entry返回. 同时自旋有限制, 64次后变成lock阻塞
- 获取到锁, 插入
— jdk1.8 —
- 和HashMap一样, 先定位到table的目标桶. 头部节点
- 如果节点为null, cas将value放进去
- 如果非null, 且hash值是-1, 说明有其他线程在扩容, 帮助扩容
- 如果非null, hash值大于0, 则用Synchronize锁住头结点插入
— jdk1.7 —
因为HashEntry和key以及value都用volatile修饰, 所以可以保证可见性
— jdk1.8 —
Node节点也是用volatile修饰
size也是并发下容易出错的点, 一边在统计数量一边在增减
— jdk1.7 —
- 先是不加锁将各个Segment汇总加起来,计算最多3次, 如果连续2次结果一样就认为是正确的结果返回
- 对每个segment加锁, 汇总计算
— jdk1.8 —
jdk1.8在统计size的时候没啥技术, 重点在于引入了counterCells这个数组. 它分为baseCount和counterCells[]两部分. 计算size的时候将两者相加
counterCells的作用就是将原本竞争锁激烈的总数, 拆成了n个部分放在数组中.
put()方法中最后会调用addCount()方法
- 如果counterCells == null 没初始化, 先尝试cas更新baseCount变量
- 如果失败了,初始化counterCells,初始容量为2, 然后把增加的数量放在counterCells数组中
- 如果counterCells != null , 随机选中一个下标, 将数值更新进去
- 如果更新baseCount和counterCell都cas失败了, 就死循环直到成功
扩容resize()方法简单的说, 就是将原本一个变量用于记录总数的, 拆分成1个基础变量和n个大小的数组, 减少了并发下的竞争冲突.
— jdk1.7 —
jdk1.7里是对当前put的Segment的HashEntry[]数组进行扩容, 方法是Segment的rehash()
跟HashMap的 resize() 没太大区别，都是迁移到另一个两倍容量的数组中，只不过是获取Segment的锁后扩容迁移
— jdk1.8 —
- jdk1.8的扩容支持并发迁移节点
- put方法中的addCount()方法后, 计算总数, 如果超过阈值, 则开始扩容, 记录参与线程数+1
- 扩容时会先在一个循环中用CAS修改transferIndex字段, 这个字段表示这个线程处理区间的上限下标(分配区间是从后往前)
- CAS修改后, 得到这个这个线程的负责区间, 开始转移
- 转移完了后, 将forwardingNode作为标识节点(hash值是-1)放在该桶位置告诉其他线程已经处理过了
- 迁移完成, 记录参与线程数-1
如果迁移时, 往一个还没迁移的桶put:
由于迁移和put都会对桶的头节点加锁synchronize, 所以会等put完后迁移
如果迁移时, get会有影响吗:
迁移的时候只是遍历旧node, 新table和新链都是new Node节点, 相当于复制, 所以不会影响
