ConcurrentHashMap源码导读之put()方法

一、简介

put()能将对应的key与value保存到map中。在ConcurrentHashMap中，key与value都不能为空，否则会抛出NullPointerException异常。如果put()时，key已经存在，则会返回put()前该key对应的value。

public static void main(String[] args) {
    ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
    map.put("key", "oldValue");
    System.out.println(map.put("key", "newValue"));
}

// 输出结果
oldValue

问题1：为什么ConcurrentHashMap中，key与value都不能为空？

二、源码

put()中只有一行代码，调用了putVal()方法，putVal()有三个参数，key、value与onlyIfAbsent。参考HashMap中的解释，"if true, don't change existing value"，如果为true，put()时如果key已经存在，就不改变当前的value，反之如果为false，就会出现上面代码中的情况，替换并返回旧的value。

1、 准备

putVal()的开始先校验了key与value。

if (key == null || value == null) throw new NullPointerException();

然后求了key的hash值。object.hashCode()是native方法，作为key的常用类String中对hashCode()进行了重写。在hashCode()之后又使用了spread()方法进行处理，得到key的hash值。

问题2：spread()具体干了什么？有什么意义？

int hash = spread(key.hashCode());

2、插入

接下来就是最重要的插入部分了，一个for循环中包含了一个if..else..结构。

如果空表时，则进行初始化操作

if (tab == null || (n = tab.length) == 0)
    tab = initTable();

问题3：initTable()的流程

如果bin为空时，则进行CAS插入

if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null,
                 new Node<K,V>(hash, key, value, null)))
        break;
}

如果有线程正在resize-扩容的过程中，则两个线程一起进行resize操作

if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);
    
static final int MOVED  = -1;

问题4：f.hash在什么时候被赋值为-1？

根据helpTransfer()的注释"Helps transfer if a resize is in progress."，推断当前if条件是判断正在进行resize操作。

问题5：helpTransfer()的流程

同步块中进行插入操作，也就是hash碰撞时的解决方案

Node<K,V> f;

synchronized (f) {
    if (tabAt(tab, i) == f){
        ...
    }
}

虽然tabAt()赋值到f过，但是多线程环境下可能此时f已经改变，所以在同步块中再进行一次判断。

• 链表中的插入

f为当前bin中的第一个元素

if (fh >= 0) {
    // 前面已经判断过了bin为空的情况，所以这里binCount最小为1
    binCount = 1;
    for (Node<K,V> e = f;; ++binCount) {
        K ek;
        // 先判断hash值再用"=="判断key是否相等
        if (e.hash == hash &&
            ((ek = e.key) == key ||
             (ek != null && key.equals(ek)))) {
             // 相等则保存原值
            oldVal = e.val;
            if (!onlyIfAbsent)
                // 赋新值
                e.val = value;
            break;
        }
        // 查找e结点的下一个节点，没有则创建
        Node<K,V> pred = e;
        if ((e = e.next) == null) {
            pred.next = new Node<K,V>(hash, key, value, null);
            break;
        }
    }
}

• 红黑树中的插入

当bin中数据结构为树时，根节点的hash值为-2

static final int TREEBIN  = -2; // hash for roots of trees

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

问题6：putTreeVal()的流程及红黑树的原理

插入后判断bin中node个数

static final int TREEIFY_THRESHOLD = 8;

if (binCount != 0) {
    // 如果node个数大于等于8则将其转为红黑树
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}

3、resize

改变map中元素的个数，如果有必要则进行resize

addCount(1L, binCount);

问题7：addCount()的流程

三、总结

遗留的问题

1. 为什么ConcurrentHashMap中，key与value都不能为空
2. spread()具体干了什么？有什么意义？
3. initTable()的流程
4. f.hash在什么时候被赋值为-1？
5. helpTransfer()的流程
6. putTreeVal()的流程及红黑树的原理
7. addCount()的流程