中级程序员题目-有了解JAVA并发容器—ConcurrentHashMap的吗?-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

中级程序员题目-有了解JAVA并发容器—ConcurrentHashMap的吗?

剑曼红尘 2020-03-25 10:40:10 118

中级程序员题目-有了解JAVA并发容器—ConcurrentHashMap的吗?

Java 容器
分享到
取消 提交回答
全部回答(1)
  • 剑曼红尘
    2020-03-25 11:21:44

    HashMap

    HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk1.7 和 1.8 中具体实现稍有 不同

    1.PNG

    其实1.7一个很明显需要优化的地方就是:

    当 Hash 冲突严重时,在桶上形成的链表会变的越来越长,这样在查询时的效 率就会越来越低;时间复杂度为 O(N)。

    因此 1.8 中重点优化了这个查询效率。

    1.8 HashMap 结构图

    2.PNG

    • JDK 1.8 对 HashMap 进行了修改:

      最大的不同就是利用了红黑树,其由数组+链表+红黑树组成。

      JDK 1.7 中,查找元素时,根据 hash 值能够快速定位到数组的具体下标, 但之后需要顺着链表依次比较才能查找到需要的元素,时间复杂度取决于链 表的长度,为 O(N)。 为了降低这部分的开销,在 JDK 1.8 中,当链表中的元素超过 8 个以后,会 将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

    • JDK 1.8 使用 Node(1.7 为 Entry) 作为链表的数据结点,仍然包含 key, value,hash 和 next 四个属性。

      红黑树的情况使用的是 TreeNode。

    • 根据数组元素中,第一个结点数据类型是 Node 还是 TreeNode 可以判断该位 置下是链表还是红黑树。

    • 核心成员变量于 1.7 类似,增加了核心变量,如下表。

    属性说明
    TREEIFY_THRESHOLD用于判断是否需要将链表转换为红黑树的阈值,默认 为 8。

    put步骤:

    1. 判断当前桶是否为空,空的就需要初始化(resize 中会判断是否进行初始 化)。

    2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空,为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。

    3. 如果当前桶有值( Hash 冲突),那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等,相等就赋值给 e,在第 8 步的时候会统一进 行赋值及返回。

    4. 如果当前桶为红黑树,那就要按照红黑树的方式写入数据。

    5. 如果是个链表,就需要将当前的 key、value 封装成一个新节点写入到当前桶的 后面(形成链表)。

    6. 接着判断当前链表的大小是否大于预设的阈值,大于时就要转换为红黑树。

    7. 如果在遍历过程中找到 key 相同时直接退出遍历。

    8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。

    9. 后判断是否需要进行扩容.

    get 方法看起来就要简单许多了。

    • 首先将 key hash 之后取得所定位的桶。

    • 如果桶为空则直接返回 null 。 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key,是 就直接返回 value。

    • 如果第一个不匹配,则判断它的下一个是红黑树还是链表。

    • 红黑树就按照树的查找方式返回值。

    • 不然就按照链表的方式遍历匹配返回值。

    从这两个核心方法(get/put)可以看出 1.8 中对大链表做了优化,修改为红黑树之 后查询效率直接提高到了 O(logn)。 但是 HashMap 原有的问题也都存在,比如在并发场景下使用时容易出现死循环。

    3.PNG

    但是为什么呢?简单分析下。 看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法,就是这里的并 发操作容易在一个桶上形成环形链表;这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环。 如下图:

    5.png

    HashTable

    • HashTable 容器使用 synchronized来保证线程安全,但在线程竞争激烈的情况下 HashTable 的效 率非常低下。

      当一个线程访问 HashTable 的同步方法时,其他线程访问 HashTable 的同步方 法可能会进入阻塞或轮询状态。

    • HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有 访问它的线程都必须竞争同一把锁,假如容器里有多把锁,每一把锁用于锁容 器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就 不会存在锁竞争,从而可以有效的提高并发访问效率,这就是 ConcurrentHashMap(JDK 1.7) 使用的 锁分段技术。

    • ConcurrentHashMap 将数据分成一段一段的存储,然后给每一段数据配一把 锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他 线程访问。

    • 有些方法需要跨段,比如 size() 和 containsValue(),它们可能需要锁定整个表 而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所 有段的锁。

    • 按顺序 很重要,否则极有可能出现死锁,在 ConcurrentHashMap 内部,段数 组是 final 的,并且其成员变量实际也是 final 的,但是,仅仅是将数组声明为 final 的并不保证数组成员也是 final 的,需要实现上的保证。这可以确保不会 出现死锁,因为获得锁的顺序是固定的。

    • HashTable 的迭代器是强一致性的,而 ConcurrentHashMap 是弱一致的。

    • ConcurrentHashMap 的 get,clear,iterator 方法都是弱一致性的。

    初识ConcurrentHashMap

    Concurrent翻译过来是并发的意思,字面理解它的作用是处理并发情况的 HashMap。

    通过前面的学习,我们知道多线程并发下 HashMap 是不安全的(如死循环),更普遍 的是多线程并发下,由于堆内存对于各个线程是共享的,而 HashMap 的 put 方法 不是原子操作,假设Thread1先 put 值,然后 sleep 2秒(也可以是系统时间片切换失 去执行权),在这2秒内值被Thread2改了,Thread1“醒来”再 get 的时候发现已经不 是原来的值了,这就容易出问题。

    6.PNG

    那么如何避免这种多线程出错的情况呢?

    常规思路就是给 HashMap 的 put 方法加锁(synchronized),保证同一个时刻只允 许一个线程拥有对 hashmap 有写的操作权限即可。然而假如线程1中操作耗时,其 他需要操作该 hashmap 的线程就需要在门口排队半天,严重影响用户体验, HashTable 就是这样子做的。

    举个生活中的例子,很多银行除了存取钱,还支持存取贵重物品,贵重物品都放在 保险箱里,把 HashMap 和 HashTable 比作银行,结构:

    7.PNG

    把线程比作人,对应的情况如下:

    8.PNG

    多线程下用 HashMap 不确定性太高,有破产的风险,不能选;用 HashTable 不会 破产,但是用户体验不太好,那么怎样才能做到多人存取既不影响他人存值,又不 用排队呢?

    有人提议搞个「银行者联盟」,多开几个像HashTable 这种「带锁」的银行就好 了,有多少人办理业务,就开多少个银行,一对一服务,这个区都是大老板,开银 行的成本都是小钱,于是「银行者联盟」成立了。 接下来的情况是这样的:比如用户A和用户B一起去银行存各自的项链,这个「银行 者联盟」操作后,然后对用户A说,1号银行现在没人你可以去那存,不用排队,然 后用户A就去1号银行存项链,1号银行把用户A接进门,马上拉闸,然后把用户A的 项链放在第x行第x个保险箱,等用户A办妥离开后,再开闸;对于用户B同理。此时 不管用户A和用户B在各自银行里面待多久都不会影响到彼此,不用担心自己的项链 被人偷换了。这就是ConcurrentHashMap的设计思路,用一个图来理解

    9.PNG

    从上图可以看出,此时锁的是对应的单个银行,而不是整个「银行者联盟」。分析 下这种设计的特点:

    多个银行组成的「银行者联盟」 当有人来办理业务时,「银行者联盟」需要确定这个人去哪个银行 当此人去到指定银行办理业务后,该银行上锁,其他人不能同时执行修改操作,直 到此人离开后解锁.

    ConcurrentHashMap源码解析

    ConcurrentHashMap 同样也分为 1.7 、1.8 版,两者在实现上略有不同。 先来看看 1.7 的实现,下面是结构图:

    11.PNG

    如图所示,是由 Segment 数组、HashEntry 组成,和 HashMap 一样,仍然是数组 加链表。主要是通过分段锁实现的。

    关于分段锁

    段Segment继承了重入锁ReentrantLock,有了锁的功能,每个锁控制的是一段, 当每个Segment越来越大时,锁的粒度就变得有些大了。

    • 分段锁的优势在于保证在操作不同段 map 的时候可以并发执行,操作同段 map 的时候,进行锁的竞争和等待。这相对于直接对整个map同步 synchronized是有优势的。

    • 缺点在于分成很多段时会比较浪费内存空间(不连续,碎片化); 操作map时竞争 同一个分段锁的概率非常小时,分段锁反而会造成更新等操作的长时间等待; 当 某个段很大时,分段锁的性能会下降。

    1.7 已经解决了并发问题,并且能支持 N 个 Segment 这么多次数的并发,但依然存 在 HashMap 在 1.7 版本中的问题。

    那就是查询遍历链表效率太低。

    因此 1.8 做了一些数据结构上的调整。 首先来看下底层的组成结构:

    12.PNG

    其实和 1.8 HashMap 结构类似,当链表节点数超过指定阈值的话,也是会转换成红 黑树的,大体结构也是一样的。 那么 JDK 1.8 ConcurrentHashMap 到底是如何实现线程安全的? 答案:其中抛弃了原有的Segment 分段锁,而采用了 CAS + synchronized 来保证 并发安全性。(cas:比较并替换)

    13.PNG

    **① 基本组成 **

    • 抛弃了 JDK 1.7 中原有的 Segment 分段锁,而采用了 CAS + synchronized 来 保证并发安全性。

    • 将JDK 1.7 中存放数据的 HashEntry 改为 Node,但作用是相同的。、 我们来看看 ConcurrentHashMap 的几个重要属性.

    14.PNG

    重要组成元素

    Node:链表中的元素为 Node 对象。他是链表上的一个节点,内部存储了 key、 value 值,以及他的下一 个节点的引用。这样一系列的 Node 就串成一串,组成一 个链表。

    ForwardingNode:当进行扩容时,要把链表迁移到新的哈希表,在做这个操作 时,会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不 保存 key 和 value,只保存了扩容后哈希表 (nextTable)的引用。此时查找相应 node 时,需要去 nextTable 中查找。

    TreeBin:当链表转为红黑树后,数组中保存的引用为 TreeBin,TreeBin 内部不保 存 key/value,他保存了 TreeNode 的 list 以及红黑树 root。

    TreeNode:红黑树的节点。

    **② put 方法过程 **

    存储结构定义了容器的 “形状”,那容器内的东西按照什么规则来放呢?换句话讲, 某个 key 是按 照什么逻辑放入容器的对应位置呢?

    我们假设要存入的 key 为对象 x,这个过程如下19.PNG 20.PNG

    1、通过对象 x 的 hashCode () 方法获取其 hashCode;

    2、将 hashCode 映射到数组的某个位置上;

    3、把该元素存储到该位置的链表中。

    15.PNG

    put 方法用来把一个键值对存储到 map 中。代码如下: 实际调用的是 putVal 方 法,第三个参数传入 false,控制 key 存在时覆盖原来的值。

    16.PNG

    17.PNG 18.PNG

    请先看完代码注释,有个大致的了解,然后我们更加详细的学习一下:

    1. 判断存储的 key、value 是否为空,若为空,则抛出异常,否则,进入步骤 2。

    2. 计算 key 的 hash 值,随后进入自旋,该自旋可以确保成功插入数据,若 table 表为空或者长度为 0,则初始化 table 表,否则,进入步骤 3。

    3. 根据 key 的 hash 值取出 table 表中的结点元素,若取出的结点为空(该桶为 空),则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则,进入 步骤 4。

    4. 若该结点的的 hash 值为 MOVED(-1),则对该桶中的结点进行转移,否则, 进入步骤 5。 5 . 对桶中的第一个结点(即 table 表中的结点)进行加锁,对该桶进行遍历,桶中 的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等,则根据标识选择是 否进行更新操作(用给定的 value 值替换该结点的 value 值),若遍历完桶仍 没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点,则直接新生 一个结点并赋值为之前后一个结点的下一个结点。进入步骤 6。

    5. 若 binCount 值达到红黑树转化的阈值,则将桶中的结构转化为红黑树存储, 后,增加 binCount 的值。

    6. 如果桶中的第一个元素的 hash 值大于 0,说明是链表结构,则对链表插入或者 更新。

    7. 如果桶中的第一个元素是 TreeBin,说明是红黑树结构,则按照红黑树的方式进 行插入或者更新。

    8. 在锁的保护下,插入或者更新完毕后,如果是链表结构,需要判断链表中元素 的数量是否超过 8(默认),一旦超过,就需要考虑进行数组扩容,或者是链表 转红黑树。

    扩容

    什么时候会扩容?

    1. 使用put()添加元素时会调用addCount(),内部检查sizeCtl看是否需要扩容。

    2. tryPresize()被调用,此方法被调用有两个调用点:

    链表转红黑树(put()时检查)时如果table容量小于64(MIN_TREEIFY_CAPACITY),则会 触发扩容。 调用putAll()之类一次性加入大量元素,会触发扩容。 addCount() addCount()与tryPresize()实现很相似,我们先以addCount()分析下扩容逻辑:

    21.PNG 23.PNG

    **1.链表转红黑树 ** 24.PNG

    首先我们要理解为什么 Map 需要扩容,这是因为我们采用哈希表存储数据,当固定 大小的哈希表存 储数据越来越多时,链表长度会越来越长,这会造成 put 和 get 的 性能下降。此时我们希望哈希表中多一些桶位,预防链表继续堆积的更长。

    ConcurrentHashMap 有链表转红黑树的操作,以提高查找的速度,红黑树时间复 杂度为 O (logn),而链表是 O (n/2),因此只在 O (logn)<O (n/2) 时才会进行转换, 也就是以 8 作为分界点。

    接下来我们分析 treeifyBin 方法代码,这个代码中会选择是把此时保存数据所在的 链表转为红黑树,还是对整个哈希表扩容。 treeifyBin 不一定就会进行红黑树转换,也可能是仅仅做数组扩容。

    22.PNG 23.PNG

    构造完TreeBin这个空节点之后,就开始构造红黑树,首先是第一个节点,左右 子节点设置为空,作为红黑树的root节点,设置为黑色,父节点为空。

    24.PNG

    然后在每次添加完一个节点之后,都会调用balanceInsertion方法来维持这是一 个红黑树的属性和平衡性。红黑树所有操作的复杂度都是O(logn),所以当元素量比 较大的时候,效率也很高。

    **数组扩容 **

    我们大致了解了 ConcurrentHashMap 的存储结构,那么我们思考一个问题,当数 组中保存的链表越来越多,那么再存储进来的元素大概率会插入到现有的链表中, 而不是使用数组中剩下的空位。 这样会造成数组中保存的链表越来越长,由此导致 哈希表查找速度下降,从 O (1) 慢慢趋近于链表 的时间复杂度 O (n/2),这显然违背 了哈希表的初衷。 所以 ConcurrentHashMap 会做一个操作, 称为扩容。也就是把数组长度变大,增 加更多的空位出来,终目的就是预防链表过长,这样查找的时间复杂度才会趋向于 O (1)。扩容的操作并不会在数组没有空位时才进行,因为在桶位快满时, 新保存元 素更大的概率会命中已经使用的位置,那么可能后几个桶位很难被使用,而链表却 越来 越长了。ConcurrentHashMap 会在更合适的时机进行扩容,通常是在数组中 75% 的位置被使用 时。 其实以上内容和 HashMap 类似,ConcurrentHashMap 此外提供了线程安全的保 证,它主要是通 过 CAS 和 Synchronized 关键字来实现,我们在源码分析中再详细 来看。

    我们做一下总结:

    1、ConcurrentHashMap 采用数组 + 链表 + 红黑树的存储结构;

    2、存入的 Key 值通过自己的 hashCode 映射到数组的相应位置;

    3、ConcurrentHashMap 为保障查询效率,在特定的时候会对数据增加长度,这个 操作叫做扩容;

    4、当链表长度增加到 8 时,可能会触发链表转为红黑树(数组长度如果小于 64, 优先扩容,具体 看后面源码分析)。

    接下来,我们的源码分析就从 ConcurrentHashMap 的构成、保存元素、哈希算 法、扩容、查找数 据这几个方面来进行 扩容后数组容量为原来的 2 倍。

    25.PNG 26.PNG

    27.PNG

    **数据迁移( 扩容时的线程安全) **

    ConcurrentHashMap 的扩容时机和 HashMap 相同,都是在 put 方法的后一步 检查是否需要扩容,如果需要则进行扩容,但两者扩容的过程完全不同, ConcurrentHashMap 扩容的方法叫做 transfer,从 put 方法的 addCount 方法进 去,就能找到 transfer 方法,transfer 方法的主要思路是:

    1. 首先需要把老数组的值全部拷贝到扩容之后的新数组上,先从数组的队尾开始 拷贝;

    2. 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷 贝到新数组时,把 原数组槽点赋值为转移节点;

    3. 这时如果有新数据正好需要 put 到此槽点时,发现槽点为转移节点,就会一直 等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化的;

    4. 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置成转移 节点;

    5. 直到所有数组数据都拷贝到新数组时,直接把新数组整个赋值给数组容器,拷 贝完成

    28.PNG 29.PNG

    30.PNG

    31.PNG 32.PNG

    33.PNG

    34.PNG 35.PNG 36.PNG 37.PNG 38.PNG 39.PNG 40.PNG 41.PNG 42.PNG

    putTreeVal()与此方法遍历方式类似不再介绍。

     ④ get 方法过程 ConcurrentHashMap 读的话,就比较简单,先获取数组的下标,然后通过判断数 组下标的 key 是 否和我们的 key 相等,相等的话直接返回,如果下标的槽点是链表 或红黑树的话,分别调用相应的 查找数据的方法,整体思路和 HashMap 很像,源 码如下:

    43.PNG

    1. 计算 hash 值。

    2. 根据 hash 值找到数组对应位置: (n – 1) & h。

    3. 根据该位置处结点性质进行相应查找。

    4. 如果该位置为 null,那么直接返回 null。 如果该位置处的结点刚好就是需要的,返回该结点的值即可。

    5. 如果该位置结点的 hash 值小于 0,说明正在扩容,或者是红黑树。

    6. 如果以上 3 条都不满足,那就是链表,进行遍历比对即可。

    ** 初始化数组 **

    数组初始化时,首先通过自旋来保证一定可以初始化成功,然后通过 CAS 设置 SIZECTL 变量的值,来保证同一时刻只能有一个线程对数组进行初始化,CAS 成功 之后,还会再次判断当前数组是否已经初始化完成,如果已经初始化完成,就不会 再次初始化,通过自旋 + CAS + 双重 check 等 手段保证了数组初始化时的线程安 全,源码如下:

    44.PNG

    里面有个关键的值 sizeCtl,这个值有多个含义。 1、-1 代表有线程正在创建 table; 2、-N 代表有 N-1 个线程正在复制 table; 3、在 table 被初始化前,代表 根据构造函数传入的值计算出的应被初始化的大小; 4、在 table 被初始化后,则被 设置为 table 大小 的 75%,代表 table 的容量(数组容量)。 initTable 中使用到 1 和 4,2 和 3 在其它方法中会有使用。下面我们可以先看下 ConcurrentHashMap 的构造方法,里面会使用上面的 3

    最后来回顾总结下HashMap和ConcurrentHashMap对比 ConcurrentHashMap 和 HashMap 两者的相同之处:

    1.数组、链表结构几乎相同,所以底层对数据结构的操作思路是相同的(只是思路 相同,底层实现 不同);

    2.都实现了 Map 接口,继承了 AbstractMap 抽象类,所以大多数的方法也都是相 同的, HashMap 有的方法,ConcurrentHashMap 几乎都有,所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时,无需关心两者之间的兼容问题

    不同点:

    1.红黑树结构略有不同,HashMap 的红黑树中的节点叫做 TreeNode,TreeNode 不仅仅有属 性,还维护着红黑树的结构,比如说查找,新增等等; ConcurrentHashMap 中红黑树被拆分成 两块,TreeNode 仅仅维护的属性和查找 功能,新增了 TreeBin,来维护红黑树结构,并负责根 节点的加锁和解锁;

    2.新增 ForwardingNode (转移)节点,扩容的时候会使用到,通过使用该节点, 来保证扩容时的线程安全。

    0 0
云原生
使用钉钉扫一扫加入圈子
+ 订阅

云原生时代,是开发者最好的时代

推荐文章
相似问题