ConcurrentHashMap 是一个线程安全的map。其他特点和hashMap一致。
相比如1.7的分段式锁的设计，1.8采用了cas和synchronized的技术。
下面来分析他各个阶段的线程安全的设计。
1、读操作
读操作，因为在Map中的设计，value值都设计成volatile，根据happen-before原则，被volatile修饰的对象，写操作一定先发生于读操作，所以读数据时，读取到的一定是最新的数据，所以这个操作无需加锁。
2、写操作
直接看代码
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//第一次put 初始化tab
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果当前槽是空的,不需要加锁。用cas替换当前槽的头节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
//如果当前槽已经被扩容（MOVED 是扩容时已经移除的标志）,一起进入扩容，如何扩容后续会分析。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//正式put 操作，先将槽的头节点锁住，剩下的操作和HashMap一致
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//当前节点超过8，进行数化
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//将map 容量加1 并且判断是否需要扩容
addCount(1L, binCount);
return null;
}
总结一下以上代码：
- 判断tab是否初始化，没有初始化则进行初始化。
- 判断要当前槽是否是空的，空的槽无需加锁（tab是volatile的,能够保证读取到的是最新头结点，当时无法保证节点后的引用是最新的），直接用CAS替换当前槽头节点。
- 判断当前槽是否已经被扩容（已经扩容的槽头节点会被替换成ForwardingNode 这个node 的hash 就是MOVED），如果发现头节点已经被替换了，说明正在扩容。则当前线程加入扩容(helpTransfer)。
- 进行put操作，将当前槽的头节点锁住。剩下的操作和HashMap一致。
- 将当前容量加1，并且计算是否需要扩容操作，如果是，则进行扩容。
3、扩容操作
扩容操作是通过拷贝底层tab,实现了CopyOnWrite特性。ConcurrHashMap在并发情况下扩容不会出现读取错误的数据。扩容的过程时候依次拷贝每一个槽，直达将全部槽都拷贝完成。
//底层数组扩容
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//nextTab 是扩容后的tab，这里初始化一下
if (nextTab == null) {
try {
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
//将要扩容的下标 设置为数组长度
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
//不知道要干什么
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt(this, TRANSFERINDEX,nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//当前槽是空的，将当前槽头节点替换为fwd
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//当前槽被其他线程处理过了，直接跳过
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {//开始拷贝数组
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
//说明①.
//头节点的hash runBit(runbit 是 hash 与上 n(数组长度)。
//举例说明一下，如果n = 16 ,当前槽下标是4.
//根据槽下标的计算公式（n-1）& hash.
//hash为4、20、36、52、68。那么hash & n 依次为0、16、0、16、0)
//在扩容后的数组中的下标依次为4、20、4、20、4
//说明hash & n 为0 的节点，在扩容后的数组下标不变，而不为0的下标为index + n (扩容前的下标加上数组长度。)
//ln(lowNode 低节点意思) hn(hignNode 高节点意思)
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
//与之前节点的高低位不同
//简单说明一下 一个槽中 如果所有的高低位是一致的，那么只需要移动头节点就够了，节点的引用并没有发生变化。
//例如 8个节点runbit 分别是0 1 0 1 1 1 1 1
//那么只需要将第二位的节点指向第四位，第一位的指向第三位，就可以完成拷贝工作。所以这里只需要记录一下 最后一次高低位变化的数据。
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
//看最后一位是高位还是低位
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
//遍历节点 重新生成 链表
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//利用cas 替换高低位节点
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
//将原来数组的头节点 替换为fwd
setTabAt(tab, i, fwd);
advance = true;
}//树的操作基本相同，唯一有区别的是扩容后需要反树化
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
总结一下以上代码：
- 如果要拷贝的数字没有初始化，则进行初始化。将拷贝的数字下标置未数据长度，倒序拷贝。
- 当前槽没有数据。直接CAS将槽的头节点替换为ForwardingNode
- 当前槽已经被别的线程修改过了 直接跳过。
- 拷贝数组，详细讲代码上注释。这里不再赘述。
- 拷贝完成 替换原来数组 头节点为ForwardingNode(这里可以说明上面 头节点为ForwardingNode ，说明当前槽已经拷贝完成，并且正在扩容)
4、删除
删除操作没有什么好说的，原理和put操作是一致的，锁住头部，控制并发。
