ConcurrentHashMap源码解析_05 get、remove方法

淩亂°似流年 2023-01-19 03:13 17阅读 0赞

*  前面几篇文章分析了并发HashMap的`put`方法及其相关方法，`transfer`方法，那么接下来本篇文章相对之前几篇难度会小一些。
 *  本篇文章介绍ConcurrentHashMap的`get`方法和`remove`方法。

--------------------

## 1、get方法 ##

`get`方法：获取元素，根据目标key所在桶的第一个元素的不同采用不同的方式获取元素，关键点在于`find()`方法的重写。

public V get(Object key) { 
        // tab 引用map.table
        // e 当前元素(用于循环遍历)
        // p 目标节点
        // n table数组长度
        // eh 当前元素hash
        // ek 当前元素key
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        // 根据key.hashCode()计算hash: 扰动运算后得到得到更散列的hash值
        int h = spread(key.hashCode());
    
        // --------------------------------------------------------------------------------
        // CASE1:
        // 如果元素所在的桶存在且里面有元素
        // 条件一：(tab = table) != null
        // true -> 表示已经put过数据，并且map内部的table也已经初始化完毕
        // false -> 表示创建完map后，并没有put过数据，map内部的table是延迟初始化的，只有第一次写数据时会触发初始化创建table逻辑
        // 条件二：(n = tab.length) > 0 如果为 true-> 表示table已经初始化
        // 条件三：(e = tabAt(tab, (n - 1) & h)) != null
        // true -> 当前key寻址的桶位有值
        // false -> 当前key寻址的桶位中是null，是null直接返回null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) { 
            // 进入if代码块内部的前置条件：当前桶位有数据
    
    		// 如果第一个元素就是要找的元素，则直接返回
            // 对比头结点hash与查询key的hash是否一致
            // 条件成立：说明头结点与查询Key的hash值完全一致
            if ((eh = e.hash) == h) { 
                // 完全比对 查询key 和 头结点的key
                // 条件成立：说明头结点就是查询数据
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    // 当e的hash值以及e对应的key都匹配目标元素时，则找到了，直接返回~
                    return e.val;
            }
            
            // --------------------------------------------------------------------------------
            // CASE2: eh < 0
            // 条件成立：即，hash小于0 分2种情况，是树或者正在扩容,需要借助find方法寻找元素，find的寻找方式依据Node的不同子类有不同的实现方式:
            // 情况一：eh=-1 是fwd结点 -> 说明当前table正在扩容，且当前查询的这个桶位的数据已经被迁移走了，需要借助fwd结点的内部方法find去查询
            // 情况二：eh=-2 是TreeBin节点 -> 需要使用TreeBin 提供的find方法查询。
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
    
            // --------------------------------------------------------------------------------
            // CASE3: 前提条件 -> CASE1和CASE2条件不满足！
    		// 说明是当前桶位已经形成链表的这种情况: 遍历整个链表寻找元素
            while ((e = e.next) != null) { 
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
    
        }
        return null;
    }

### 1.1 ForwardingNode 内部类(FWD结点) ###

在`get`方法CASE2中，`eh < 0`会分2中情况：

*  情况一：`eh=-1` 是fwd结点 -> 说明当前table正在扩容，且当前查询的这个桶位的数据已经被迁移走了，需要借助fwd结点的内部方法find去查询。
 *  情况二：`eh = -2` 是TreeBin节点 -> 需要使用TreeBin 提供的`find`方法查询。

下面就分析一下情况一，即当前桶位中是fwd结点。我们来分析一下FWD这个内部类，以及其内部的`find`方法：

static final class ForwardingNode<K,V> extends Node<K,V> { 
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) { 
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    
        // fwd结点的find方法：
        Node<K,V> find(int h, Object k) { 
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            // tab 一定不为空：整个ConcurrentHashMap源码中，只有一个地方实例化ForwardingNode，就是在transfer迁移数据方法中执行了：ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);（当某个桶位数据处理完毕后，将此桶位设置为fwd节点，其它写线程或读线程看到后，会有不同逻辑）
            Node<K,V>[] tab = nextTable;
            
            // ------------------------------------------------------------------------------
            // 自旋1
            outer: for (;;) { 
                // n 表示为扩容而创建的新表的长度
                // e 表示在扩容而创建新表时，使用寻址算法得到的桶位头结点
                Node<K,V> e; int n;
    
                // 条件一：永远不成立
                // 条件二：永远不成立
                // 条件三：永远不成立
                // 条件四：在新扩容表中重新路由定位 hash 对应的头结点
                // true -> 1.在oldTable中对应的桶位在迁移之前就是null
                // false -> 2.扩容完成后，有其它写线程，将此桶位设置为了null
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;
    
                // ---------------------------------------------------------------------------
                // 自旋2
                // 前置条件：扩容后的表对应hash的桶位一定不是null，e为此桶位的头结点
                // e可能为哪些node类型？
                // 1.node 类型
                // 2.TreeBin 类型
                // 3.FWD类型
                for (;;) { 
                    // eh 新扩容后表指定桶位的当前节点的hash
                    // ek 新扩容后表指定桶位的当前节点的key
                    int eh; K ek;
                    // CASE1条件成立：说明新扩容后的表，当前命中桶位中的数据，即为查询想要数据。
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        // 直接将e返回~
                        return e;
    
                    // CASE2: eh < 0 时
                    // 1.TreeBin 类型 
                    // 2.FWD类型（新扩容的表，在并发很大的情况下，可能在此方法再次拿到FWD类型），即可能又发生了扩容
                    if (eh < 0) { 
                        // 判断是否是FWD结点
                        if (e instanceof ForwardingNode) { 
                            // 是FWD结点
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            // 跳转到自旋1
                            continue outer;
                        }
                        else// 不是FWD结点
                            // 说明此桶位 为 TreeBin 节点，使用TreeBin.find 查找红黑树中相应节点。
                            return e.find(h, k);
                    }
    
                    // 前置条件：当前桶位头结点 并没有命中查询，说明此桶位是链表
                    // 1.将当前元素指向链表的下一个元素
                    // 2.判断当前元素的下一个位置是否为空
                    // true -> 说明迭代到链表末尾，未找到对应的数据，返回Null
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }

小节：

（1）hash到元素所在的桶；

（2）如果桶中第一个元素就是该找的元素，直接返回；

（3）如果是树或者正在迁移元素，则调用各自Node子类的`find()`方法寻找元素；

（4）如果是链表，遍历整个链表寻找元素；

（5）获取元素没有加锁；

## 2、remove方法 ##

`remove`方法：删除元素跟添加元素一样，都是先找到元素所在的桶，然后采用分段锁的思想锁住整个桶，再进行操作。

public V remove(Object key) { 
    	// 调用替换节点方法
        return replaceNode(key, null, null);
    }
    
    /** * 结点替换： * 参数1：Object key -> 就表示当前结点的key * 参数2：V value -> 要替换的目标值 * 参数3：Object cv（compare Value） -> * 如果cv不为null，则需要既比对key，还要比对cv，这样个参数都一致，才能替换成目标值 */
    final V replaceNode(Object key, V value, Object cv) { 
        // 计算key经过扰动运算后得到的hash
        int hash = spread(key.hashCode());
        // 自旋
        for (Node<K,V>[] tab = table;;) { 
            // f表示桶位头结点
            // n表示当前table数组长度
            // i表示hash命中桶位下标
            // fh表示桶位头结点hash
            Node<K,V> f; int n, i, fh;
    
            // ----------------------------------------------------------------------------
            // CASE1：
            // 条件一：tab == null 
            // true -> 表示当前map.table尚未初始化.. 
            // false -> 表示当前map.table已经初始化
            // 条件二：(n = tab.length) == 0 
            // true -> 表示当前map.table尚未初始化.. 
            // false -> 已经初始化
            // 条件三：(f = tabAt(tab, i = (n - 1) & hash)) == null 
            // true -> 表示命中桶位中为null，直接break
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                // 如果目标key所在的桶不存在，跳出循环返回null
                break;
    		
            // ----------------------------------------------------------------------------
            // CASE2：
            // 前置条件CASE2 ~ CASE3：当前桶位不是null
            // 条件成立：fwd结点，说明当前table正在扩容中，当前是个写操作，所以当前线程需要协助table完成扩容。
            else if ((fh = f.hash) == MOVED)
                // 如果正在扩容中，则协助扩容
                tab = helpTransfer(tab, f);
            
    		// ----------------------------------------------------------------------------
            // CASE3:
            // 前置条件CASE2 ~ CASE3：当前桶位不是null
            // 当前桶位是一个有数据的桶位，桶中可能是 "链表"也可能是"红黑树"TreeBin
            else { 
                // 保留替换之前的数据引用
                V oldVal = null;
                // 校验标记,在下面的CASEn中的if判断使用：标记是否处理过
                boolean validated = false;
                // 加锁当前桶位头结点，加锁成功之后会进入代码块。
                synchronized (f) { 
                    // 判断sync加锁是否为当前桶位头节点，防止其它线程，在当前线程加锁成功之前，修改过桶位 的头结点，导致锁错对象！
                    
                    // --------------------------------------------------------------------
            		// CASE4: tabAt(tab, i) == f 再次验证当前桶第一个元素是否被修改过
                    // 条件成立：说明当前桶位头结点仍然为f，其它线程没修改过！
                    if (tabAt(tab, i) == f) { 
                        // --------------------------------------------------------------------
            			// CASE5: fh >= 0 
                        // 条件成立：说明桶位为链表或者单个node
                        if (fh >= 0) { 
                            // 校验标记置为true
                            validated = true;
    
                            // e 表示当前循环处理结点
                            // pred 表示当前循环节点的上一个节点
                            Node<K,V> e = f, pred = null;
    						// 遍历链表寻找目标节点
                            for (;;) { 
                                // 表示当前节点key
                                K ek;
                                
                                // ------------------------------------------------------------
            					// CASE6:
                                // 条件一：e.hash == hash 
                                // true->说明当前节点的hash与查找节点hash一致
                                // 条件二：((ek = e.key) == key || (ek != null && key.equals(ek)))
                                // CASE6的if条件成立，说明key 与查询的key完全一致。
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) { 
                                    // 找到了目标节点：当前节点的value，
                                    V ev = e.val;
    
                                    // -----------------------------------------------------
            						// CASE7: 检查目标节点旧value是否等于cv
                                    // 条件一：cv == null 
                                    // true -> 替换的值为null那么就是一个删除操作
                                    // 条件二：cv == ev || (ev != null && cv.equals(ev)) 
                                    // true -> 那么是一个替换操作
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) { 
                                        // 删除 或者 替换
                                        // 将当前节点的值 赋值给 oldVal 后续返回会用到~
                                        oldVal = ev;
    
                                        // 目标value不等于null
                                        // 如果条件成立：说明当前是一个替换操作
                                        if (value != null)
                                            // 直接替换
                                            e.val = value;
                                        // 条件成立：说明当前节点非头结点
                                        else if (pred != null)
                                            // 如果前置节点不为空，删除当前节点：
                                            // 让当前节点的上一个节点，指向当前节点的下一个节点。
                                            pred.next = e.next;
    									// 条件成里：说明当前节点即为头结点
                                        else
                                            // 如果前置节点为空，说明是桶中第一个元素，删除之：
                                            // 只需要将桶位设置为头结点的下一个节点。
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                // 遍历到链表尾部还没找到元素，跳出循环
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
    					
                        // --------------------------------------------------------------------
            			// CASE8: f instanceof TreeBin
                        // 条件成立：TreeBin节点。
                        else if (f instanceof TreeBin) { 
                            // 校验标记置为true
                            validated = true;
    
                            // 转换为实际类型 TreeBin t
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            // r 表示 红黑树根节点
                            // p 表示 红黑树中查找到对应key 一致的node
                            TreeNode<K,V> r, p;
    
                            // 遍历树找到了目标节点：
                            // 条件一：(r = t.root) != null 理论上是成立
                            // 条件二：TreeNode.findTreeNode 以当前节点为入口，向下查找key（包括本身节点）
                            // true->说明查找到相应key 对应的node节点，会赋值给p
                            if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) { 
                                // 保存p.val 到pv
                                V pv = p.val;
    
                                // 检查目标节点旧value是否等于cv：
                                // 条件一：cv == null 成立：不必对比value，就做替换或者删除操作
                                // 条件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：说明“对比值”与当前p节点的值 一致
                                if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) { 
                                    // 替换或者删除操作
                                    oldVal = pv;
    
                                    // 如果value不为空则替换旧值
                                    // 条件成立：替换操作
                                    if (value != null)
                                        p.val = value;
    
                                    // 如果value为空则删除元素
                                    // 删除操作
                                    else if (t.removeTreeNode(p))
                                        // 如果删除后树的元素个数较少则退化成链表
                                        // t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数较少
                                        setTabAt(tab, i, untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                // ----------------------------------------------------------------------------
                // CASEn: 如果处理过，不管有没有找到元素都返回
                // 当其他线程修改过桶位头结点时，当前线程 sync 头结点 锁错对象时，validated 为false，会进入下次for自旋:
                if (validated) { 
                    // 如果找到了元素，返回其旧值
                    if (oldVal != null) { 
                        // 替换的值 为null，说明当前是一次删除操作，oldVal ！=null 成立，说明删除成功，更新当前元素个数计数器。
                        // 如果要替换的值为空，元素个数减1
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        
    	// 没找到元素返回空
        return null;
    }

小节：

（1）计算hash；

（2）如果所在的桶不存在，表示没有找到目标元素，返回；

（3）如果正在扩容，则协助扩容完成后再进行删除操作；

（4）如果是以链表形式存储的，则遍历整个链表查找元素，找到之后再删除；

（5）如果是以树形式存储的，则遍历树查找元素，找到之后再删除；

（6）如果是以树形式存储的，删除元素之后树较小，则退化成链表；

（7）如果确实删除了元素，则整个map元素个数减1，并返回旧值；

（8）如果没有删除元素，则返回null；

--------------------

本篇文章结束，ConcurrentHashMap的大部分知识点分析完毕，下面一篇文章最后再分析一下TreeBin就收尾了！