finnish 是一个标志,如果为 true 则说明整张表的迁移操作已经全部完成了,我们只需要重置 table 的引用并将 nextTable 赋为空即可。否则,CAS 式的将 sizeCtl 减一,表示当前线程已经完成了任务,退出扩容操作。
如果退出成功,那么需要进一步判断是否还有其他线程仍然在执行任务。
我们说过 resizeStamp(n) 返回的是对 n 的一个数据校验标识,占 16 位
而
的值为 16,那么位运算后,整个表达式必然在右边空出 16 个零。也正如我们所说的,sizeCtl 的高 16 位为数据校验标识,低 16 为表示正在进行扩容的线程数量
(resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2
表示当前只有一个线程正在工作,相对应的,如果
(sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT
说明当前线程就是最后一个还在扩容的线程,那么会将 finishing 标识为 true,并在下一次循环中退出扩容方法。
这一块的难点在于对 sizeCtl 的各个值的理解,关于它的深入理解,这里推荐一篇文章。
着重理解位操作
看到这里,真的为 Doug Lea 精妙的设计而折服,针对于多线程访问问题,不但没有拒绝式得将他们阻塞在门外,反而邀请他们来帮忙一起工作。
好了,我们一路往回走,回到我们最初分析的 putVal 方法。接着前文的分析,当我们根据 hash 值,找到对应的桶结点,如果发现该结点为 ForwardingNode 结点,表明当前的哈希表正在扩容和 rehash,于是将本线程送进去帮忙扩容。否则如果是普通的桶结点,于是锁住该桶,分链表和红黑树的插入一个节点,具体插入过程类似 HashMap,此处不再赘述。
当我们成功的添加完成一个结点,最后是需要判断添加操作后是否会导致哈希表达到它的阈值,并针对不同情况决定是否需要进行扩容,还有 CAS 式更新哈希表实际存储的键值对数量。这些操作都封装在 addCount 这个方法中,当然 putVal 方法的最后必然会调用该方法进行处理。下面我们看看该方法的具体实现,该方法主要做两个事情。一是更新 baseCount,二是判断是否需要扩容。
//第一部分,更新 baseCount private final void addCount(long x, int check) { CounterCell[] as; long b, s; //如果更新失败才会进入的 if 的主体代码中 //s = b + x 其中 x 等于 1 if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; //高并发下 CAS 失败会执行 fullAddCount 方法 if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null ||!(uncontended =U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } 这一部分主要完成的是对 baseCount 的 CAS 更新。 //第二部分,判断是否需要扩容 if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } }
这部分代码也是比较简单的,不再赘述。
至此,对于 put 方法的源码分析已经完全结束了,很复杂但也很让人钦佩
下面我们简单看看 remove 方法的实现。
8.4.2 remove 方法实现并发删除
无非就是先定位再删除
首先遍历整张表的桶结点,如果表还未初始化或者无法根据参数的 hash 值定位到桶结点,那么将返回 null
如果定位到的桶结点类型是ForwardingNode 结点,调用 helpTransfer 协助扩容
否则就老老实实的给桶加锁,删除一个节点
最后会调用 addCount 方法 CAS 更新 baseCount 的值。
8.4.3 size
size 方法的作用是为我们返回哈希表中实际存在的键值对的总数
可能你会有所疑问,ConcurrentHashMap 中的 baseCount 属性不就是记录的所有键值对的总数吗?直接返回它不就行了吗?
之所以没有这么做,是因为我们的 addCount 方法用 CAS 更新 baseCount,但很有可能在高并发的情况下,更新失败,那么这些节点虽然已经被添加到哈希表中了,但是数量却没有被统计.
还好,addCount 方法在更新 baseCount 失败的时候,会调用 fullAddCount 将这些失败的结点包装成一个 CounterCell 对象,保存在 CounterCell 数组中;
那么整张表实际的 size 其实是 baseCount 加上 CounterCell 数组中元素的个数.
8.4.4 get
get 方法可以根据指定的键,返回对应的键值对,由于是读操作,所以不涉及到并发问题
源码也是比较简单的
8.4.5 clear
clear 方法将删除整张哈希表中所有的键值对,删除操作也是一个桶一个桶的进行删除
public void clear() { long delta = 0L; // negative number of deletions int i = 0; Node<K,V>[] tab = table; while (tab != null && i < tab.length) { int fh; Node<K,V> f = tabAt(tab, i); if (f == null) ++i; else if ((fh = f.hash) == MOVED) { tab = helpTransfer(tab, f); i = 0; // restart } else { synchronized (f) { if (tabAt(tab, i) == f) { Node<K,V> p = (fh >= 0 ? f :(f instanceof TreeBin) ?((TreeBin<K,V>)f).first : null); //循环到链表或者红黑树的尾部 while (p != null) { --delta; p = p.next; } //首先删除链、树的末尾元素,避免产生大量垃圾 //利用CAS无锁置null setTabAt(tab, i++, null); } } } } if (delta != 0L) addCount(delta, -1); }