解析ConcurrentHashMap: get、remove方法分析

前面几篇文章分析了并发HashMap的put方法及其相关方法,transfer方法,那么接下来本篇文章相对之前几篇难度会小一些。

本篇文章介绍ConcurrentHashMapget方法和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());
java    // --------------------------------------------------------------------------------
    // 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代码块内部的前置条件:当前桶位有数据
java		// 如果第一个元素就是要找的元素,则直接返回
        // 对比头结点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;
        }
java        // --------------------------------------------------------------------------------
        // 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;
java        // --------------------------------------------------------------------------------
        // CASE3: 前提条件 -> CASE1和CASE2条件不满足!
		// 说明是当前桶位已经形成链表的这种情况: 遍历整个链表寻找元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
java    }
    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;
    }
java    // 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;
java        // ------------------------------------------------------------------------------
        // 自旋1
        outer: for (;;) {
            // n 表示为扩容而创建的新表的长度
            // e 表示在扩容而创建新表时,使用寻址算法得到的桶位头结点
            Node<K,V> e; int n;
java            // 条件一:永远不成立
            // 条件二:永远不成立
            // 条件三:永远不成立
            // 条件四:在新扩容表中重新路由定位 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;
java            // ---------------------------------------------------------------------------
            // 自旋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;
java                // 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);
                }
java                // 前置条件:当前桶位头结点 并没有命中查询,说明此桶位是链表
                // 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);
}
java/**
 * 结点替换:
 * 参数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;
java        // ----------------------------------------------------------------------------
        // 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;
java        // ----------------------------------------------------------------------------
        // CASE2:
        // 前置条件CASE2 ~ CASE3:当前桶位不是null
        // 条件成立:fwd结点,说明当前table正在扩容中,当前是个写操作,所以当前线程需要协助table完成扩容。
        else if ((fh = f.hash) == MOVED)
            // 如果正在扩容中,则协助扩容
            tab = helpTransfer(tab, f);
java		// ----------------------------------------------------------------------------
        // CASE3:
        // 前置条件CASE2 ~ CASE3:当前桶位不是null
        // 当前桶位是一个有数据的桶位,桶中可能是 "链表"也可能是"红黑树"TreeBin
        else {
            // 保留替换之前的数据引用
            V oldVal = null;
            // 校验标记,在下面的CASEn中的if判断使用:标记是否处理过
            boolean validated = false;
            // 加锁当前桶位头结点,加锁成功之后会进入代码块。
            synchronized (f) {
                // 判断sync加锁是否为当前桶位头节点,防止其它线程,在当前线程加锁成功之前,修改过桶位 的头结点,导致锁错对象!
java                // --------------------------------------------------------------------
        		// CASE4:  tabAt(tab, i) == f 再次验证当前桶第一个元素是否被修改过
                // 条件成立:说明当前桶位头结点仍然为f,其它线程没修改过!
                if (tabAt(tab, i) == f) {
                    // --------------------------------------------------------------------
        			// CASE5:  fh >= 0
                    // 条件成立:说明桶位为链表或者单个node
                    if (fh >= 0) {
                        // 校验标记置为true
                        validated = true;
java                        // e 表示当前循环处理结点
                        // pred 表示当前循环节点的上一个节点
                        Node<K,V> e = f, pred = null;
						// 遍历链表寻找目标节点
                        for (;;) {
                            // 表示当前节点key
                            K ek;
java                            // ------------------------------------------------------------
        					// 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;
java                                // -----------------------------------------------------
        						// 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;
java                                    // 目标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;
                        }
                    }
java                    // --------------------------------------------------------------------
        			// CASE8:  f instanceof TreeBin
                    // 条件成立:TreeBin节点。
                    else if (f instanceof TreeBin) {
                        // 校验标记置为true
                        validated = true;
java                        // 转换为实际类型 TreeBin t
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        // r 表示 红黑树根节点
                        // p 表示 红黑树中查找到对应key 一致的node
                        TreeNode<K,V> r, p;
java                        // 遍历树找到了目标节点:
                        // 条件一:(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;
java                            // 检查目标节点旧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;
java                                // 如果value不为空则替换旧值
                                // 条件成立:替换操作
                                if (value != null)
                                    p.val = value;
java                                // 如果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;
            }
        }
    }
java	// 没找到元素返回空
    return null;
}

小节

(1)计算hash;

(2)如果所在的桶不存在,表示没有找到目标元素,返回;

(3)如果正在扩容,则协助扩容完成后再进行删除操作;

(4)如果是以链表形式存储的,则遍历整个链表查找元素,找到之后再删除;

(5)如果是以树形式存储的,则遍历树查找元素,找到之后再删除;

(6)如果是以树形式存储的,删除元素之后树较小,则退化成链表;

(7)如果确实删除了元素,则整个map元素个数减1,并返回旧值;

(8)如果没有删除元素,则返回null;

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

时间: 2021-06-09

解析ConcurrentHashMap: 预热(内部一些小方法分析)

前面一篇文章中介绍了并发HashMap的主要成员属性,内部类和构造函数,下面在正式分析并发HashMap成员方法之前,先分析一些内部类中的字方法函数: 首先来看下ConcurrentHashMap内部类Node中的hash成员属性值的计算方法spread(int h): static class Node<K,V> implements Map.Entry<K,V> { final int hash;// 该属性是通过spread(int h)方法计算得到~ final K key

解析ConcurrentHashMap:成员属性、内部类、构造方法分析

1.简介 ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素.相比于同样线程安全的HashTable来说,效率等各方面都有极大地提高. 在学习ConcurrentHashMap源码之前,这里默认大家已经读过HashMap源码,了解LongAdder原子类.红黑树.先简单介绍下 ConcurrentHashMap的整体流程: 整体流程跟HashMap比较类似,大致是以下几步: (1)如果桶数组未初始化,则初始化: (2)如果

解析ConcurrentHashMap: put方法源码分析

上一章:预热(内部一些小方法分析) put()方法是并发HashMap源码分析的重点方法,这里涉及到并发扩容,桶位寻址等等- JDK1.8 ConcurrentHashMap结构图: 1.put方法源码解析 // 向并发Map中put一个数据 public V put(K key, V value) { return putVal(key, value, false); } // 向并发Map中put一个数据 // Key: 数据的键 // value:数据的值 // onlyIfAbsent:

解析ConcurrentHashMap: 红黑树的代理类(TreeBin)

前一章是get.remove方法分析,喜欢的朋友点击查看.本篇为ConcurrentHashMap源码系列的最后一篇,来分析一下TreeBin 红黑树代理节点的源码: 1.TreeBin内部类分析 TreeBin是红黑树的代理,对红黑树不太了解的,可以参考: static final class TreeBin<K,V> extends Node<K,V> { // 红黑树根节点 TreeNode<K,V> root; // 链表的头节点 volatile TreeNo

解析ConcurrentHashMap: transfer方法源码分析(难点)

上一篇文章介绍过put方法以及其相关的方法,接下来,本篇就介绍一下transfer这个方法(比较难),最好能动手结合着源码进行分析,并仔细理解前面几篇文章的内容~ 注:代码分析的注释中的CASE0.CASE1- ,这些并没有直接关联关系,只是为了给每个if逻辑判断加一个标识,方便在其他逻辑判断的地方进行引用而已. 再复习一下并发Map的结构图: 1.transfer方法 transfer方法的作用是:迁移元素,扩容时table容量变为原来的两倍,并把部分元素迁移到其它桶nextTable中.该方

解析Mybatis判断表达式源码分析

在我们开发过程中用 Mybatis 经常会用到下面的例子 Mapper如下 Map<String ,String > testArray(@Param("array") String [] array); XMl中的sql如下 <select id="testArray" resultType="map"> select * from t_ams_ac_pmt_dtl where cpt_pro=#{cptProp} &l

Java并发编程之Condition源码分析(推荐)

Condition介绍 上篇文章讲了ReentrantLock的加锁和释放锁的使用,这篇文章是对ReentrantLock的补充.ReentrantLock#newCondition()可以创建Condition,在ReentrantLock加锁过程中可以利用Condition阻塞当前线程并临时释放锁,待另外线程获取到锁并在逻辑后通知阻塞线程"激活".Condition常用在基于异步通信的同步机制实现中,比如dubbo中的请求和获取应答结果的实现. 常用方法 Condition中主要的

thinkphp3.2.0 setInc方法 源码全面解析

我们先来看一下setInc的官方示例: 需要一个字段和一个自增的值(默认为1) 我们通过下面这个例子来一步步分析他的底层是怎么实现的: <?php namespace Home\Controller; use Think\Controller; class TestController extends Controller { public function test() { $tb_test = M('test'); $tb_test->where(['id'=>1])->set

Java并发系列之ConcurrentHashMap源码分析

我们知道哈希表是一种非常高效的数据结构,设计优良的哈希函数可以使其上的增删改查操作达到O(1)级别.Java为我们提供了一个现成的哈希结构,那就是HashMap类,在前面的文章中我曾经介绍过HashMap类,知道它的所有方法都未进行同步,因此在多线程环境中是不安全的.为此,Java为我们提供了另外一个HashTable类,它对于多线程同步的处理非常简单粗暴,那就是在HashMap的基础上对其所有方法都使用synchronized关键字进行加锁.这种方法虽然简单,但导致了一个问题,那就是在同一时间

Vue 中 template 有且只能一个 root的原因解析(源码分析)

引言 今年, 疫情 并没有影响到各种面经的正常出现,可谓是络绎不绝(学不动...).然后,在前段时间也看到一个这样的关于 Vue 的问题, 为什么每个组件 template 中有且只能一个 root? 可能,大家在平常开发中,用的较多就是 template 写 html 的形式.当然,不排除用 JSX 和 render() 函数的.但是,究其本质,它们最终都会转化成 render() 函数.然后,再由 render() 函数转为 Vritual DOM (以下统称 VNode ).而 rende

java 源码分析Arrays.asList方法详解

最近,抽空把java Arrays 工具类的asList 方法做了源码分析,在网上整理了相关资料,记录下来,希望也能帮助读者! Arrays工具类提供了一个方法asList, 使用该方法可以将一个变长参数或者数组转换成List . 其源代码如下: /** * Returns a fixed-size list backed by the specified array. (Changes to * the returned list "write through" to the arr

jQuery插件-jRating评分插件源码分析及使用方法

该插件被广泛应用于各种需要评分的页面当中,今天作为学习,把源码拿出来分析一下,顺便学习其使用方法. 一.插件使用一览. 复制代码 代码如下: <div> <div>第一个例子</div> <div id="16_1" class="myRating"></div> </div> 复制代码 代码如下: <link href="Script/jRating/jRating.jquer

Spring SpringMVC在启动完成后执行方法源码解析

关键字:spring容器加载完毕做一件事情(利用ContextRefreshedEvent事件) 应用场景:很多时候我们想要在某个类加载完毕时干某件事情,但是使用了spring管理对象,我们这个类引用了其他类(可能是更复杂的关联),所以当我们去使用这个类做事情时发现包空指针错误,这是因为我们这个类有可能已经初始化完成,但是引用的其他类不一定初始化完成,所以发生了空指针错误,解决方案如下: 1.写一个类继承spring的ApplicationListener监听,并监控ContextRefresh

RateLimiter 源码分析

俗话说得好,缓存,限流和降级是系统的三把利剑.刚好项目中每天早上导出数据时因调订单接口频率过高,订单系统担心会对用户侧的使用造成影响,让我们对调用限速一下,所以就正好用上了. 常用的限流算法有2种:漏桶算法和令牌桶算法. 漏桶算法 漏桶算法:请求先进入"桶"中,然后桶以一定的速率处理请求.如果请求的速率过快会导致桶溢出.根据描述可以知道,漏桶算法会强制限制请求处理的速度.任你请求的再快还是再慢,我都是以这种速率来处理. 但是对于很多情况下,除了要求能够限制平均处理速度外,还要求能允许一

jQuery源码分析-03构造jQuery对象-工具函数

作者:nuysoft/高云 QQ:47214707 EMail:nuysoft@gmail.com 声明:本文为原创文章,如需转载,请注明来源并保留原文链接. 读读写写,不对的地方请告诉我,多多交流共同进步,本章的的PDF等本章写完了发布. jQuery源码分析系列的目录请查看 http://nuysoft.iteye.com/blog/1177451,想系统的好好写写,目前还是从我感兴趣的部分开始,如果大家有对哪个模块感兴趣的,建议优先分析的,可以告诉我,一起学习. 3.4 其他静态工具函数