ConcurrentHashMap源码解析(二)之------put()方法。

ConcurrentHashMap是一个支持高并发集合常用的集合之一。
而put()方法是并发里面的重点。

put()方法入口:

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

1.hashMap是允许key和value都为空的而在ConcurrentHashMap中是不允许的

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

2.通过spread()方法可以让高位也能参与到寻址运算

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

3.binCount的作用是在桶位中的所属链表的下标位置
0表示当前桶位为null, node可以直接放着
2 表示当前桶位已经树化为红黑树

    int binCount = 0;

4.进入自旋方法定义的属性

  // f 表示 桶位的头节点
            Node<K,V> f;
            // n  表示散列表数组长度
            // i 表示key通过寻址计算后,得到的桶位下标
            // fn 表示桶位头节点的hash值
            int n, i, fh;

5接下来就是四种情况的if判断
CASE1: 条件成立表示当前map中的table尚未初始化

 if (tab == null || (n = tab.length) == 0)
                // 需要初始化
                tab = initTable();

6.这里又涉及到了initTable()方法主要是使用CAS原理。
tab表示map.table的引用

    Node<K,V>[] tab;

sc:表示临时局部的sizeCtl值

     int sc;

判断table为null,当前散列表尚未初始化

(tab = table) == null || tab.length == 0

当sizeCtl < 0 大概率为-1其他线程正在进行创建table的过程当前线程没有竞争到初始化table的锁。

再次判断table为null防止其他线程已经初始化完毕然后当前线程再次初始化导致数据丢失。

(tab = table) == null || tab.length == 0

最终赋值给map.table

table = tab = nt;

并给sc赋值下次扩容的触发条件

 sc = n - (n >>> 2);

下面进入CASE2
i=(n-1) &hash 表示key使用路由寻址算法得到key 对应table数组的下标位置;
f :tabAt获取指定桶位的头结点

(f = tabAt(tab, i = (n - 1) & hash)) == null

进入到CASE2代码块前置条件:当前table数组i桶位是null时
使用CAS方式设置指定数组i桶位为Node且期望值为null时,
CAS操作成功直接break
CAS操作失败表示当前线程之前有其他线程先进入向指定i桶位设置值了

 if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;     

CASE3
表示当前桶位头结点为FWD结点表示当前map处于扩容中
桶位的头结点一定不是null.

(fh = f.hash) == MOVED

CASE4当前桶位可能是链表也可能是红黑树代理节点

使用sync加锁给“头结点”理论上是头结点

synchronized (f)

当fh >= 0 表示当前桶位是一个普通的链表

fh >= 0

迭代循环当前桶位的链表e是每次循环处理节点

Node<K,V> e = f;; ++binCount

条件成立表示当前桶位是红黑树代理节点TreeBin

f instanceof TreeBin

p是红黑树如果与你插入节点的key有冲突点的话则putTreeVal()方法会返回冲突节点的引用

 Node<K,V> p;

强制设置binCount为2因为binCount <= 1时候会有其他含义这里设置为了2

binCount = 2;

当前桶位不为null可能是红黑树也可能是链表

binCount != 0

如果binCount >= 8 表示处理的桶位一定是链表

binCount >= TREEIFY_THRESHOLD

调用转化为链表为红黑树的方法

 treeifyBin(tab, i);

四个CASE结束后会进行addCount()方法
1.统计当前table一共有多少数据。
2.判断是否拿到扩容值标准触发扩容

  addCount(1L, binCount);

源码注释粘贴

  final V putVal(K key, V value, boolean onlyIfAbsent) {
        // key 和value不能为空
        if (key == null || value == null) throw new NullPointerException();

        // 通过spread方法可以让高位也能参与到寻址运算
        int hash = spread(key.hashCode());
        //表示当前k-v 封装成node后插入到指定桶位后在桶位中的所属链表的下标位置
        // 0 表示当前桶位为 null,node可以直接放着
        // 2 表示当前桶位已经树化为红黑树。
        int binCount = 0;

        // 自旋;
        // tab引用map对象的table
        for (Node<K,V>[] tab = table;;) {
            // f 表示 桶位的头节点
            Node<K,V> f;
            // n  表示散列表数组长度
            // i 表示key通过寻址计算后,得到的桶位下标
            // fn 表示桶位头节点的hash值
            int n, i, fh;

            // CASE1: 成立表示: 当前map中的table尚未初始化
            if (tab == null || (n = tab.length) == 0)
                // 需要初始化
                tab = initTable();

            // CASE2: 
            // i 表示key 使用路由寻址算法得到key 对应 table 数组的下标位置 tabAt 获取指定桶位的头节点 f
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

                //进入到CASE2代码块的前置条件当前table数组i桶位是null时
                // 使用CAS方式设置指定数组i桶位 为 Node且期望值时null.
                // CAS 操作成功表示ok 直接break
                // CAS操作失败: 表示当前线程之前有其他线程先进入向指定i桶位设置值了。
                // 当前线程只能再次自旋去走其他逻辑。

                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }

            // CASE3:
            // 条件成立: 表示当前桶位头节点 为 FWD节点表示当前map处于扩容中
            // 桶位的头节点一定不是null。
            else if ((fh = f.hash) == MOVED)
                // 看到fwd节点后当前节点有义务帮助当前map对象完成迁移数据的工作。
                tab = helpTransfer(tab, f);

            //CASE 4:
            // 当前桶位 可能是 链表 也可能是 红黑树代理节点 TreeBin
            else {
                // 当插入key存在时会将旧值返回给oldVal返回给put方法调用
                V oldVal = null;

                // 使用sync 加锁给"头节点",理论上是头节点
                synchronized (f) {
                    // 为什么再次对比 看看当前桶位的头节点是否为之前获取的头节点
                    // 为了避免其他线程将该桶位的头节点修改掉导致当前线程从sync加锁就有问题了之后的操作都不用做。
                    if (tabAt(tab, i) == f) { // 条件成立说明加锁的对象OK。
                        // 当fh >= 0 说明当前桶位是一个普通的链表;
                        if (fh >= 0) {
                            //1.当前插入key 与链表当中所有的都不一致时当前的插入操作是追加到链表的末尾binCount表示链表长度。
                            //2.当前插入key与链表当中的某个元素key一致时当前插入操作可能是替换了。binCount表示冲突位置(binCount -1 )
                            binCount = 1;

                            // 迭代循环当前桶位的链表e是每次循环处理节点。
                            for (Node<K,V> e = f;; ++binCount) {
                                // 当前循环节点 key
                                K ek;
                                // 条件一:e.hash == hash 表示循环当前元素的hash值与插入节点的hash值一致需要进一步判断
                                // 条件2.1: (ek = e.key) == key   (ek != null && key.equals(ek)))
                                // 说明当前循环的节点与插入节点的key一致发生冲突了。
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    // 将当前循环的元素的值 赋值给 oldVal
                                    oldVal = e.val;

                                    //
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }

                                // 当前元素与插入元素的key 不一致时会走下面
                                //1.更新循环节点为 当前节点的下一个节点
                                //2.判断下一个节点是否为 null如果是null说明当前节点已经是队尾了插入数据需要追加到队尾的后面。
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        // 前置条件该桶位一定不是链表
                        // 条件成立表示当前桶位是红黑树代理节点TreeBin
                        else if (f instanceof TreeBin) {
                            // 当前桶位已经是红黑树
                            // p表示红黑树如果与你插入节点的key 有冲突节点的话则putTreeVal 方法会返回冲突节点的引用
                            Node<K,V> p;
                            // 强制设置binCount为2,因为binCount <= 1时候会有其他含义所以这里设置为了2.
                            binCount = 2;

                            // putTreeVal() 往红黑树插入节点
                            // 条件1成立: 说明当前插入节点的key与红黑树中的某个节点的key一致冲突了
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                // 将冲突节点赋值给 oldVal;
                                oldVal = p.val;
                                //重写
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }

                // 说明当前桶位不为null可能是红黑树也可能是链表
                if (binCount != 0) {
                    // 如果binCount >= 8 表示处理的桶位一定是链表
                    if (binCount >= TREEIFY_THRESHOLD)
                        // 调用转化为链表为红黑树的方法
                        treeifyBin(tab, i);

                    // 说明当前线程插入的数据与原有key-v冲突需要将原数据返回给调用者。
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }

        // 1.统计当前table一共有多少数据。
        //2.判断是否拿到扩容值标准触发扩容;
        addCount(1L, binCount);
        return null;
    }

initTable()源码粘贴

 private final Node<K,V>[] initTable() {
        // tab 表示 map.table的引用
        Node<K,V>[] tab;
        // sc 表示临时局部的sizeCtl值
        int sc;

        // 条件是table 为 null。 当前散列表尚未初始化
        while ((tab = table) == null || tab.length == 0) {

            if ((sc = sizeCtl) < 0)
                // 大概率为 -1 其他线程正在进行创建table的过程当前线程没有竞争到初始化table的锁
                Thread.yield(); // lost initialization race; just spin

            // 1.sizeCtl = 0; 表示创建table数组时 使用DEFAULT_CAPACITY为大小
            // 2.如果table未初始化表示初始化大小;
            // 3.如果table已经初始化表示下次扩容时的触发条件(阈值)
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    // 再次判断防止其他线程已经初始化完毕然后当前线程再次初始化....导致丢失数据。
                    // 如果条件成立 说明其他线程都没有进入过这个if块当前线程就是具备初始化table权利了。
                    if ((tab = table) == null || tab.length == 0) {

                        // sc >0 创建table时使用sc为指定大小否则使用16作为默认值
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];

                        // 最终赋值给 map.table
                        table = tab = nt;

                        // n 右移2位。 = 1/4  sc = n- 1/4n = 3/4 n = 0.75n;
                        // sc 表示下次扩容时的触发条件
                        sc = n - (n >>> 2);
                    }
                } finally {
                    // 如果当前线程是第一次创建map.table的线程的话sc表示是下一次扩容的阈值
                    // 表示当前线程并不是第一次创建map.table 当前线程进入到else if 块时将sizeCtl 设置为了-1那么
                    // 这时需要将其修改为 进入时的值。
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }