java concurrent-ConcurrentHashMap
一、数据结构
下图(来自网络):
简要说明:
1.segments数组
2.segment-散列表
3.table-segment散列表的桶数组
4.HashEntry-segment散列表发生冲突时候,使用链表解决冲突
锁粒度-segment散列表
segment加锁位置
put和remove方法
作用:
多线程的竞争只在同一个segment中,且get请求不需要加锁操作
二、方法说明(下面源码openjdk1.7):
2.1 put
2.1.1 ensureSegment
1.确保k位置上有segment对象已经创建好,即保证k位置散列表存在。
2.设置方式通过cas(CompareAndSwapObject,实际是通过机器指令chmxchg),完成原子性的比较赋值操作
2.1.2 segment.put(key, hash, value, false)
1.入口处的tryLock()和finally的unlock(),表明该方法需要加锁
2.红色1模块是key为已经存在的,则更换值,结束
3.红色2模块为key为新值,则会放到散列表的正确位置,
其中如果发现值达到了某个阀值,会调用rehash方法,
该方法会创建新的table[],但是其中旧的所用的HashEntry都会进行拷贝克隆,
这样做的好处是使get函数无需加锁,因此新的segment内部的table[]的不会被rehash函数导致不一致性
最后将新的table[]更新到旧的table[]上
2.2 remove
2.2.1 segment.remove(key, hash, null)
1.入口tryLock和finally的unlock,表明方法需要加锁
2.红块1只将remove的obj的pre的next指向obj的next,而不去置空obj.next,这样便不会影响get的查询过程
2.3 get-无锁
1.getObjectVolatile,表明当前获取该数据必须从内存中加载数据,而不被优化成可能使用上次存储到寄存器数据
三、jdk1.8
jdk1.8中,数据结构不再是segments了,就只是一个散列表Node[]
锁粒度为Node[i],即相同的index才会发生锁竞争
冲突竞争,由链表(8个以下冲突)->红黑树(8个以上冲突)