驽马十驾 驽马十驾

驽马十驾,功在不舍

目录
简单聊聊JDK8下ConcurrentHashMap的put方法
/  

简单聊聊JDK8下ConcurrentHashMap的put方法

开篇

最近又看了一些关于Java8下ConcurrentHashMap的分析,自己也尝试通过源码来进行一些理解,这里总结性的记录下一些收获,更详细的资料,网上很多,再此就不造轮子了。

本文主要记录put方法相关的几个点:

  1. sizectl的作用?
  2. 初始化tab数组时,如何保证线程安全的?
  3. 初始化tab[i]的时候,如何保证线程安全的?
  4. 遍历的时候,如何保证线程安全?
  5. addCount,如何保证线程安全的。
  6. JDK7的乐观+悲观策略。

路漫漫其修远兮,吾将上下而求索!

sizeCtl的作用

首先看其定义,其中关键字时 volatile 保证了线程可见性。

private transient volatile int sizeCtl;

该字段主要起到了一个 状态描述扩容阈值作用。

  • 等于 0: 表示默认值
  • 大于 0:扩容阈值
  • 等于 -1:正在初始化
  • 小于 -1: 多个线程正在扩容

ConcurrentHashMap中的几个操作中就利用了该字段的状态做判定,接着看。

初始化数组

HashMap的结构最外层是数组,这点大家应该都知道了,那么在当这个数组为null的时候,需要对其初始化,CCHM(ConcurrentHashMap)是如何做的了?

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0) //判定小于0
                Thread.yield(); //交出CPU时间片
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //通过cas赋值为-1,表示初始化中。
                //init...
            }
        }
    }

上述代码中,有3个关键:

  1. if ((sc = sizeCtl) < 0) 判定当前是否有线程正在初始化,如果有,那么通过 Thread.yield()时间片。
  2. 通过CAS赋值,代码U.compareAndSwapInt(this, SIZECTL, sc, -1).
  3. 外层的while循环保证必须初始化成功再退出。

初始化tab[i]

初始化完成tab后,通过key的hashcode计算出当前值存在再下标为i的数组中了,第一次插入的时候,tab[i]肯定为null,那么如何初始化了?

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }

其中casTabAt为:

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

标准的CAS赋值,保证只会被初始化一次。

遍历判定

找到对应的数组下标后,就需要进行遍历链表或者红黑树,找出该值是否已经存在。

java.util.concurrent.ConcurrentHashMap#putVal

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;
                                }

大致代码如所述:很容易看出来,通过了关键字synchronized锁住了列表第一个值。

addCount

addCount的作用是维护 CCHM的size,其代码如下所示:

private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {

U.compareAndSwapLong通过这个很明显看出来是CAS

JDK7的乐观和悲观

最后简单提下JDK7在put和size的实现,很有趣,其内部是:先是乐观尝试,达到一定的阈值都没有成功就转为悲观的加锁操作。

scanAndLockForPut代码如下:

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
            while (!tryLock()) {
                HashEntry<K,V> f; // to recheck first below
                if (retries < 0) {
                    if (e == null) {
                        if (node == null) // speculatively create node
                            node = new HashEntry<K,V>(hash, key, value, null);
                        retries = 0;
                    }
                    else if (key.equals(e.key))
                        retries = 0;
                    else
                        e = e.next;
                }
                else if (++retries > MAX_SCAN_RETRIES) { //开始悲观了。。。
                    lock(); //锁住,等待被唤醒。
                    break;
                }

size的代码如下:

public int size() {
        //.....
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // 强行锁住
                }
                //不满足重试次数就直接获取每一个segment的里面的大小并求和。

很有意思吧,先乐观后悲观。

总结

上述这些就是最近看JDK7和JDK8的源码的一些个人理解。

其实结合原理来看,并不难,但是让我去写这些代码,哎。。。

路漫漫其修远兮,吾将上下而求索!

骐骥一跃,不能十步。驽马十驾,功在不舍。