ConcurrentHashMap

ConcurrentHashMap概述: 

(1.7) ConcurrentHashMap 最多可以允许16个(segment的个数)同时的写并发. 读是不需要加锁的. 所以当读操作和写操作overlap的时候,读到的数值是最新的写的结果. 

---

1.7 的实现:

采用了Segment 数组 + HashEntry数组的组织方式. Segment本身就是ReentrantLock自带锁的功能.

插入实现:

1) 根据key的hash值确定segment的index; 

2) 如果segment没有初始化,则通过CAS赋值进行初始化;  

3) 多个线程同时对同一个segment的插入操作由于锁的存在,同时只有个线程可以拿到锁执行插入,当一个线程执行完之后会唤醒另外一个线程. 

size()的实现: 

首先进行不加锁的计算,最多3次,如果本次计算和前一次一次样则立刻返回,否则加锁的方式计算. 每次计算都是累加所有segment的size. 

---

1.8  实现

基本结构: 

采用了node数组+链表的方式实现. 

node数组的初始化,node数组中元素的初始化都是使用了大量CAS来做并发控制. 

put操作:

1) 根据key计算hash值; 看是否需要初始化node数组; 

2)根据hash值定位到node数组的index, 如果为空则使用CAS操作创建新节点; 

3)对当前index的node加synchronized锁, 也就说1.8中ConcurrentHashMap的最大并发度是node数组的大小; 比1.7的segment大很多; 

4)对当前链表进行遍历和插入操作,如果是红黑树节点则进行红黑树操作; 

size的实现:

1) 本身维护了一个volatile size变量来记录size; 当有添加和删除的时候会更新这个变量; 

2) 如果多个线程同时使用CAS更新size变量的时候, 对于失败的线程,可以继续使用counterCell变量记录一下本次的size的变化; counterCell的原理和longAddler类似; 

3)最终统计size的时候会把size,然后再加上counterCell中的值;