文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

深入浅出ConcurrentHashMap内部实现

2024-12-03 06:01

关注

ConcurrentHashMap可以说是目前使用最多的并发数据结构之一,作为如此核心的基本组件,不仅仅要满足我们功能的需求,更要满足性能的需求。而实现一个高性能的线程安全的HashMap也绝非易事。

ConcurrentHashMap作为JDK8的内部实现,一个成功的典范,有着诸多可以让我们学习和致敬的地方。

我全局在项目中搜索这个类的时候,发现大量项目代码和源码都用到了,为什么他会这么吃香呢?到底是道德的....呸。

下面我们就来扒一扒,ConcurrentHashMap的内部实现,来体会一下它的精妙之处吧!

ConcurrentHashMap的内部数据结构

在JDK8中, ConcurrentHashMap的内部实现发生了天翻地覆的变化。这里依据JDK8,来介绍一下ConcurrentHashMap的内部实现。

从静态数据结构上说,ConcurrentHashMap包含以下内容:

int sizeCtl

这是一个多功能的字段,可以用来记录参与Map扩展的线程数量,也用来记录新的table的扩容阈值

CounterCell[] counterCells

用来记录元素的个数,这是一个数组,使用数组来记录,是因为避免多线程竞争时,可能产生的冲突。使用了数组,那么多个线程同时修改数量时,极有可能实际操作数组中不同的单元,从而减少竞争。

Node[] table

实际存放Map内容的地方,一个map实际上就是一个Node数组,每个Node里包含了key和value的信息。

Node[] nextTable

当table需要扩充时,会把新的数据填充到nextTable中,也就是说nextTable是扩充后的Map。

以上就是ConcurrentHashMap的核心元素,其中最值得注意的便是Node,Node并非想象中如此简单,下面的图展示了Node的类族结构:

可以看到,在Map中的Node并非简单的Node对象,实际上,它有可能是Node对象,也有可能是一个Treebin或者ForwardingNode。

那什么时候是Node,什么时候是TreeBin,什么时候又是一个ForwardingNode呢?

其实在绝大部分场景中,使用的依然是Node,从Node数据结构中,不难看出,Node其实是一个链表,也就是说,一个正常的Map可能是长这样的:

上图中,绿色部分表示Node数组,里面的元素是Node,也就是链表的头部,当两个元素在数据中的位置发生冲突时,就将它们通过链表的形式,放在一个槽位中。

当数组槽位对应的是一个链表时,在一个链表中查找key只能使用简单的遍历,这在数据不多时,还是可以接受的,当冲突数据比较多少,这种简单的遍历就有点慢了。

因此,在具体实现中,当链表的长度大于等于8时,会将链表树状化,也就是变成一颗红黑树。如下图所示,其中一个槽位就变成了一颗树,这就是TreeBin(在TreeBin中使用TreeNode构造整科树)。

 

当数组容量快满时,即超过75%的容量时,数组还需要进行扩容,在扩容过程中,如果老的数组已经完成了复制,那么就会将老数组中的元素使用ForwardingNode对象替代,表示当前槽位的数据已经处理了,不需要再处理了,这样,当有多个线程同时参与扩容时,就不会冲突。

put()方法的实现

现在来看一下作为一个HashMap最为重要的方法put():

它负责将给定的key和value对存入HashMap,它的工作主要有以下几个步骤:

  1. 如果没有初始化数组,则尝试初始化数组
  2. 如果当前正在扩容,则参与帮助扩容(调用helpTransfer()方法)
  3. 将给定的key,value 放入对应的槽位
  4. 统计元素总数
  5. 触发扩容操作

根据以上主要4个步骤,来依次详细说明一下:

如果没有初始化数组,则尝试初始化数组

初始化数据会生成一个Node数组:

  1. Node[] nt = (Node[])new Node[n]; 

默认情况下,n为16。同时设置sizeCtl为·n - (n >>> 2); 这意味着sizeCtl为n的75%,表示Map的size,也就是说ConcurrentHashMap的负载因子是0.75。(为了避免冲突,Map的容量是数组的75%,超过这个阈值,就会扩容)

如果当前正在扩容,则参与帮助扩容

  1. else if ((fh = f.hash) == MOVED) 
  2.     tab = helpTransfer(tab, f); 

如果一个节点的hash是MOVE,则表示这是一个ForwardingNode,也就是当前正在扩容中,为了尽快完成扩容,当前线程就会参与到扩容的工作中,而不是等待扩容操作完成,如此紧密细致的操作,恰恰是ConcurrentHashMap高性能的原因。

而代码中的f.hash==MOVE语义上等同于f instanceof ForwardingNode,但是使用整数相等的判断的效率要远远高于instanceof,所以,这里也是一处对性能的极限优化。

将给定的key,value 放入对应的槽位

在大部分情况下,应该会走到这一步,也就是将key和value放入数组中。在这个操作中会使用大概如下操作:

  1. Node f; 
  2. synchronized (f) { 
  3.      if(所在槽位是一个链表) 
  4.          插入链表 
  5.      else if(所在槽位是红黑树) 
  6.          插入树 
  7.      if(链表长度大于8[TREEIFY_THRESHOLD]) 
  8.          将链表树状化 

可以看到,这使用了synchronized关键字,锁住了Node对象。由于在绝大部分情况下,不同线程大概率会操作不同的Node,因此这里的竞争应该不会太大。

并且随着数组规模越来越大,竞争的概率会越来越小,因此ConcurrentHashMap有了极好的并行性。

统计元素总数

为了有一个高性能的size()方法,ConcurrentHashMap使用了单独的方法来统计元素总数,元素数量统计在CounterCell数组中:

  1. CounterCell[] counterCells; 
  2. @sun.misc.Contended static final class CounterCell { 
  3.     volatile long value; 
  4.     CounterCell(long x) { value = x; } 

CounterCell使用伪共享优化,具有很高的读写性能。counterCells中所有的成员的value相加,就是整个Map的大小。这里使用数组,也是为了防止冲突。

如果简单使用一个变量,那么多线程累加一个计数器时,难免要有竞争,现在分散到一个数组中,这种竞争就小了很多,对并发就更加友好了。

累加的主要逻辑如下:

  1. if (as == null || (m = as.length - 1) < 0 || 
  2.     //不同线程映射到不同的数组元素,防止冲突 
  3.     (a = as[ThreadLocalRandom.getProbe() & m]) == null || 
  4.     //使用CAS直接增加对应的数据 
  5.     !(uncontended = 
  6.       U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) 
  7.     //如果有竞争,在这里会重试,如果竞争严重还会将CounterCell[]数组扩容,以减少竞争 

触发扩容操作

最后,ConcurrentHashMap还会检查是否需要扩容,它会检查当前Map的大小是否超过了阈值,如果超过了,还会进行扩容。

ConcurrentHashMap的扩容过程非常巧妙,它并没有完全打乱当前已有的元素位置,而是在数组扩容2倍后,将一半的元素移动到新的空间中。

所有的元素根据高位是否为1分为low节点和high节点:

  1. //n是数组长度,数组长度是2的幂次方,因此一定是100 1000 10000 100000这种二进制数字 
  2. //这里将low节点串一起, high节点串一起 
  3. if ((ph & n) == 0) 
  4.     ln = new Node(ph, pk, pv, ln); 
  5. else 
  6.     hn = new Node(ph, pk, pv, hn); 

接着,重新放置这些元素的位置:

  1. //low节点留在当前位置 
  2. setTabAt(nextTab, i, ln); 
  3. //high节点放到扩容后的新位置,新位置距离老位置n 
  4. setTabAt(nextTab, i + n, hn); 
  5. //扩容完成,用ForwardingNode填充 
  6. setTabAt(tab, i, fwd); 

下图显示了 从8扩充到16时的可能得一种扩容情况,注意,新的位置总是在老位置的后面n个槽位(n为原数组大小)

这样做的好处是,每个元素的位置不需要重新计算,进行查找时,由于总是会对n-1(一定是一个类似于1111 11111 111111这样的二进制数)按位与,因此,high类的节点自然就会出现在+n的位置上。

get()方法的实现

与put()方法相比,get()方法就比较简单了。步骤如下:

  1. 根据hash值 得到对应的槽位 (n - 1) & h
  2. 如果当前槽位第一个元素key就和请求的一样,直接返回
  3. 否则调用Node的find()方法查找
  4. 对于ForwardingNode 使用的是 ForwardingNode.find()
  5. 对于红黑树 使用的是TreeBin.find()
  6. 对于链表型的槽位,依次顺序查找对应的key

写在最后

ConcurrentHashMap可以说是并发设计的典范,在JDK8中,ConcurrentHashMap可以说是再一次脱胎换骨,全新的架构和实现带来了飞一般的体验(JDK7中的ConcurrentHashMap还是采用比较骨板的segment实现的),细细品读,还是有不少的收获。

他和HashMap的区别,优劣势对比,这也是常考的考点,所以大家不管是为了了解、工作还是面试,都应该好好的熟悉一下。

多线程系列我会继续更新,我是敖丙,你知道的越多,你不知道的越多,我们江湖见。

 

来源:三太子敖丙内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯