ConcurrentHashMap源码分析(02)-putVal()方法

前言

上一章节，我们对构造方法进行了分析，接下来我们要分析的是元素的插入。在Map接口的方法定义里面，put()方法的职责就是插入元素。而Concurrent.put()方法又直接调用了putVal()方法，那么我们分析的重点将放在putVal()上面。

put()方法

我们先来看看put()方法是否如前言所描述那般。根据下面的源码，我们得到了证明。

public V put(K key, V value) {
    return putVal(key, value, false);
}

putVal()方法

先来看看这个方法的源码。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 1. 如果key或者value为null，抛出空指针异常，这点和`HashMap`有所不同
    if (key == null || value == null) throw new NullPointerException();
    // 2. 根据key的hashCode()，重新生成hash
    int hash = spread(key.hashCode());
    int binCount = 0;
    // 3. 这儿是空循环，也就是自旋操作
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 3.1. 如果`table`为null或长度为0，需要对`table`进行初始化。从上一节构造方法的分析来看，构造方法并不会初始化`table`。初始化`table`延迟到`putVal()`方法
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 3.2. 如果hash没有冲突，则使用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;                   // no lock when adding to empty bin
        }
        // 3.3. 如果hash冲突了，且槽里面第一个元素的hash为MOVED(-1)。则说明槽里面的元素为`ForwardingNode`对象，有其他线程正在扩容。当前线程通过`helpTransfer`进行辅助扩容，扩容完成之后再进行插入操作
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        // 3.4. 如果hash冲突了，且槽里面第一个元素的hash不为-1，需要对槽里面首元素进行加锁，然后将元素加进去
        else {
            V oldVal = null;
            // 对首元素加锁，相比于jdk7来说，又有了进一步的性能提升
            synchronized (f) {
                // 这儿需要再次判断槽里面的首元素是否为f。因为在添加元素的时候有可能同时又有其他线程在移除元素，这种情况需要自旋来重新插入
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 槽里面的首元素是f，且首元素的hash是非负数，说明槽的数据结构为链表，依次遍历插入即可
                        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) { // 槽里的首元素是f，且首元素是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;
                        }
                    }
                }
            }
            // binCount表示槽里面元素的个数，如果个数>=8，则需要将链表结构转换为红黑树结构，以此来提高性能
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 4. 通过`addCount()`方法进行扩容
    addCount(1L, binCount);
    return null;
}

我们来分析一下这个方法，该方法做了下面这些事情

如果key或者value为null，抛出空指针异常，这点和HashMap有所不同
根据key的hashCode()，重新生成hash
这儿是空循环，也就是自旋操作
1. 如果table为null或长度为0，需要对table进行初始化。从上一节构造方法的分析来看，构造方法并不会初始化table。初始化table延迟到putVal()方法
2. 如果hash没有冲突，则使用CAS插入
3. 如果hash冲突了，且槽里面第一个元素的hash为MOVED(-1)。则说明槽里面的元素为ForwardingNode对象，有其他线程正在扩容。当前线程通过helpTransfer进行辅助扩容，扩容完成之后再进行插入操作
4. 如果hash冲突了，且槽里面第一个元素的hash不为-1，需要对槽里面首元素进行加锁，然后将元素加进去
通过addCount()方法进行扩容

为了加深我们对于putVal()的理解，我们需要进一步分析该方法内部调用的几个关键方法

spread()
initTable()
tabAt()
casTabAt()
helpTransfer()
addCount()

1. spread()

static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

这个方法将hash的高位扩展到低位，同时强制最高位为0（可能是为了让hash值保持为非负数吧）。该方法做了下面几件事情

我们将原int叫做A
这儿将原int右移16位得到的int叫做B，则B的高16位则全为0
A和B异或，得到C，C的高位和A的高位相同
C再和HASH_BITS按位与，得到结果D，D的符号位为0

2. initTable()

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // table为null或者table长度为0，才进行初始化
    while ((tab = table) == null || tab.length == 0) {
        // sizeCtl为负数，说明有其他线程正在初始化table，当前线程让出cpu时间片，等待其他线程初始化完成
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // 通过CAS设置sizeCtl为-1成功之后，则说明当前线程抢占到了锁，需要进行真正的初始化操作
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // 这儿还需要对table进行二次校验。
                // 因为CAS设置成功，有可能是由于table已经初始化完成了。
                // 如果是这种情况，当前线程不需要再次初始化
                if ((tab = table) == null || tab.length == 0) {
                    // 当前线程通过`new Node[]`的方式进行`table`初始化
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    // 这儿的`n - (n >>> 2);`写得非常牛逼。
                    // 右移1位，大小折半，右移2位，大小折1/4。
                    // 这儿原始int减去1/4，则为3/4，即：0.75*原int，
                    // 正好是HashMap里面默认的负载因子
                    // 至于为什么要用位移和减法，而不直接使用除法，楼主认为是基于性能的考虑，除法的性能比加减法和位移要低得多。
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc; // 扩容保护
            }
            break;
        }
    }
    return tab;
}

该方法初始化table，table的size记录在sizeCtl变量中。该方法采用自旋+CAS的方式实现了乐观锁，相比于悲观锁，带来了非常大的性能提升。

3. tabAt()

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

该方法目的是取tab数组中，下标为i的元素。那么为啥要这样写呢？在理解之前，我们先来看看取数组元素的方法。

首先，我们知道数组元素在内存里面是连续存放的；
其次，数组元素存放的是引用地址，而非具体的值；
最后，数组取元素的方式可以通过数组地址+数组元素偏移量的方式来获取。

((long)i << ASHIFT) + ABASE这个表达式中，(long)i << ASHIFT表示偏移量，ABASE表示数组地址。

另外为啥又要使用getObjectVolatile()呢，是因为在并发的情况下，我们需要保证数组元素的内存可见性。

4. 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);
}

关键的地方和tabAt()相同，不同的在于其功能。该方法用于对数组指定下标的元素进行CAS赋值。

5. 扩容方法

helpTransfer()和addCount()涉及到扩容相关的知识点，本章暂且不表，后续会单独开一节来详细说明。

总结

至此我们分析了putVal()整体的结构。不过对于扩容和辅助扩容相关知识点，我们并没有分析，而是一笔带过。原因在于扩容的知识相当得复杂，即使单开一节来分析都稍显不够。为了保证本节的简单些和清晰性，我们留待后续来说明。

即使只是分析了putVal()的皮毛，我们也能从中看到Doug Lea对于细节和性能处理方式的周全思虑，楼主阅读之后可谓是受益匪浅~