ConcurrentHashMap

BichonCode 等级 493 0 0

一、关键属性

1. sizeCtl

** 作用**:_transient、_volatile修饰,用于数组初始化与扩容控制,只有一个线程能初始化散列表,但是可以多个线程参与扩容。

| sizeCtl = -1 | 表示当前table正在初始化(有线程在创建table数组),当前线程需要自旋等待.. -1是一把锁,哪个线程能把sizeCtl设置成-1,哪个线程就拥有初始化散列表的权限。CAS设置-1成功后,还要判断table是否为空,不为空的话就表示创建完成了,不能再创建了。 | | --- | --- | | sizeCtl < 0 && sizeCtl != -1 | 表示当前table数组正在进行扩容 ,高16位表示:扩容的标识戳 低16位表示:(1 + nThread) 当前参与并发扩容的线程数量 | | sizeCtl = 0 | 表示创建table数组时 使用DEFAULT_CAPACITY为大 | | sizeCtl > 0 | _如果table未初始化,表示初始化大小 _ 2. 如果table已经初始化,表示下次扩容时的 触发条件(阈值)_ |

二、关键方法

1. putVal()方法分析

  1. binCoun_t:_表示当前k-v 封装成node后插入到指定桶位后,在桶位中的所属链表的下标位置
0 表示当前桶位为null,node可以直接放着
2 表示当前桶位已经可能是红黑树
>= 8 说明处理的桶位一定是链表,需要转化成红黑树

2. addCount()方法分析

作用:

  1. 统计当前table一共有多少数据
  2. 判断是否达到扩容阈值标准,触发扩容。

与HashMap的区别

  1. CHP的key和value不能是null;

三、常见面试题

1. JDK1.8中的ConcurrentHashMap是如何保证线程安全的?

ConcurrentHashMap

或者说:

  1. 储存Map数据的数组时被volatile关键字修饰,一旦被修改,其他线程就可见修改。因为是数组存储,所以只有改变数组内存值是才会触发volatile的可见性
  2. 如果put操作时hash计算出的槽点内没有值,采用自旋+CAS保证put一定成功,且不会覆盖其他线程put的值
  3. 如果put操作时节点正在扩容,即发现槽点为转移节点,会等待扩容完成后再进行put操作,保证扩容时老数组不会变化
  4. 对槽点进行操作时会锁住槽点,保证只有当前线程能对槽点上的链表或红黑树进行操作
  5. 红黑树旋转时会锁住根节点,保证旋转时线程安全

2. JDK7和JDK8中的ConcurrentHashMap不同点。

ConcurrentHashMap

3. 扩容期间在未迁移到的hash桶插入数据会发生什么?

答:只要插入的位置扩容线程还未迁移到,就可以插入,当迁移到该插入的位置时,就会阻塞等待插入操作完成再继续迁移 。

4.1 正在迁移的hash桶遇到 get 操作会发生什么?

答:在扩容过程期间形成的 hn 和 ln链 是使用的类似于复制引用的方式,也就是说 ln 和 hn 链是复制出来的,而非原来的链表迁移过去的,所以原来 hash 桶上的链表并没有受到影响,因此如果当前节点有数据,还没迁移完成,此时不影响读,能够正常进行。 如果当前链表已经迁移完成,那么头节点会被设置成fwd节点,此时get线程会帮助扩容。

4.2 正在迁移的hash桶遇到 put/remove 操作会发生什么?

如果当前链表已经迁移完成,那么头节点会被设置成fwd节点,此时写线程会帮助扩容,如果扩容没有完成,当前链表的头节点会被锁住,所以写线程会被阻塞,直到扩容完成。

5. 如果 lastRun 节点正好在一条全部都为高位或者全部都为低位的链表上,会不会形成死循环?

答:在数组长度为64之前会导致一直扩容,但是到了64或者以上后就会转换为红黑树,因此不会一直死循环 。

6. 扩容后 ln 和 hn 链不用经过 hash 取模运算,分别被直接放置在新数组的 i 和 n + i 的位置上,那么如何保证这种方式依旧可以用过 h & (n - 1) 正确算出 hash 桶的位置?

答:如果 fh & n-1 = i ,那么扩容之后的 hash 计算方法应该是 fh & 2n-1 。 因为 n 是 2 的幂次方数,所以 如果 n=16, n-1 就是 1111(二进制), 那么 2n-1 就是 11111 (二进制) 。 其实 fh & 2n-1 和 fh & n-1 的值区别就在于多出来的那个 1 => fh & (10000) 这个就是两个 hash 的区别所在 。而 10000 就是 n 。所以说 如果 fh 的第五 bit 不是 1 的话 fh & n = 0 => fh & 2n-1 == fh & n-1 = i 。 如果第5位是 1 的话 。fh & n = n => fh & 2n-1 = i+n 。

7. 并发情况下,各线程中的数据可能不是最新的,那为什么 get 方法不需要加锁?

答:get操作全程不需要加锁是因为Node的成员val是用volatile修饰的,在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。。

8.1 ConcurrentHashMap 和 Hashtable 的区别?

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable是采用 数组+链表 的形式。 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

8.2 ConcurrentHashMap 和 HashMap 的相同点和不同点

相同之处:

  • 都是数组 +链表+红黑树的数据结构(JDK8之后),所以基本操作的思想一致
  • 都实现了Map接口,继承了AbstractMap 操作类,所以方法大都相似,可以相互切换 不同之处:
  • ConcurrentHashMap 是线程安全的,多线程环境下,无需加锁直接使用
  • ConcurrentHashMap 多了转移节点,主要用户保证扩容时的线程安全

9. 扩容过程中,读访问能否访问的到数据?怎么实现的?

可以的。当数组在扩容的时候,会对当前操作节点进行判断,如果当前节点还没有被设置成fwd节点,那就可以进行读写操作,如果该节点已经被处理了,那么当前线程也会加入到扩容的操作中去。

10.为什么超过冲突超过8才将链表转为红黑树而不直接用红黑树?

  • 默认使用链表, 链表占用的内存更小
  • 正常情况下,想要达到冲突为8的几率非常小,如果真的发生了转为红黑树可以保证极端情况下的效率

11. ConcurrentHashMap 和HashMap的扩容有什么不同?

  • HashMap的扩容是创建一个新数组,将值直接放入新数组中,JDK7采用头链接法,会出现死循环,JDK8采用尾链接法,不会造成死循环
  • ConcurrentHashMap 扩容是从数组队尾开始拷贝,拷贝槽点时会锁住槽点,拷贝完成后将槽点设置为转移节点。所以槽点拷贝完成后将新数组赋值给容器

12. ConcurrentHashMap 是如何发现当前槽点正在扩容的?

ConcurrentHashMap 新增了一个节点类型,叫做转移节点,当我们发现当前槽点是转移节点时(转移节点的 hash 值是 -1),即表示 Map 正在进行扩容.

13. 描述一下 CAS 算法在 ConcurrentHashMap 中的应用

  • CAS是一种乐观锁,在执行操作时会判断内存中的值是否和准备修改前获取的值相同,如果相同,把新值赋值给对象,否则赋值失败,整个过程都是原子性操作,无线程安全问题
  • ConcurrentHashMap 的put操作是结合自旋用到了CAS,如果hash计算出的位置的槽点值为空,就采用CAS+自旋进行赋值,如果赋值是检查值为空,就赋值,如果不为空说明有其他线程先赋值了,放弃本次操作,进入下一轮循环

14. 我们都知道,并发情况下,各线程中的数据可能不是最新的,那为什么 get 方法不需要加锁?

答:get操作全程不需要加锁是因为Node的成员val是用volatile修饰的 。

收藏
评论区

相关推荐

3 手写Java HashMap核心源码
手写Java HashMap核心源码 上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。 HashMap
7 二分搜索树的原理与Java源码实现
1 折半查找法 了解二叉查找树之前,先来看看折半查找法,也叫二分查找法 在一个有序的整数数组中(假如是从小到大排序的),如果查找某个元素,返回元素的索引。 如下: int arr new int{1,3,4,6,8,9}; 在 arr 数组中查找6这个元素,查到返回对应的索引,没有找到就返回1 思想很简单: 1 先找到数组中间元素ta
Java的其他Map
一、LinkedHashMap 1.1 应用场景 HashMap是无序的,当我们希望有顺序地去存储keyvalue时,就需要使用LinkedHashMap了。 1.2 插入顺序和访问顺序 LinkedHashMap默认的构造参数是默认  插入顺序的,就是说你插入的是什么顺序,读出来的就是什么顺序,但是也有访问顺序,就是说你访问了一个key,这个
ConcurrentHashMap
一、关键属性 1. sizeCtl 作用:_transient、_volatile修饰,用于数组初始化与扩容控制,只有一个线程能初始化散列表,但是可以多个线程参与扩容。 | sizeCtl 1 | _表示当前table正在初始化(有线程在创建table数组),当前线程需要自旋等待.._  1是一把锁,哪个线程能把sizeCtl设置成1,哪
HashMap的理解
HashMap在Map.Entry静态内部类实现中存储keyvalue对。HashMap使用哈希算法,在put和get方法中,它使用hashCode()和equals()方法。当我们通过传递keyvalue对调用put方法的时候, HashMap使用Key hashCode()和哈希算法来找出存储keyvalue对的索引。Entry存储在LinkedL
算法笔记:红黑树
红黑树,一种平衡二叉树,最为著名的应用就是C STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质: 1. 每个节点是红色或者黑色的; 2. 根节点是黑色的; 3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少); 4. 如
拿下面试!HashMap源码解析!!
拿下面试!HashMap源码解析!! HashMap的设计思想 HashMap的底层结构 本文主要是讲解jdk1.8中的HashMap源码,会对jdk1.7中的HashMap做一些简单的讲解用来和jdk1.8中的HashMap进行对比。 我们先通过下图来理解HashMap的底层结构: (https
Redis三种集群模式-Cluster集群模式
Redis三种集群模式Cluster集群模式一、  在之前有看到过redis集群部署的三种方案,不过性能最高的还是redis官方推荐的rediscluster,性能最高,下面介绍一下rediscluster这种模式。1、redisclusterA、采用去中心化的思想,没有中心节点的说法,它使用hash slot方式将16348个hash slot覆盖到所有节
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
JDK13的特性和JDK的历史你知道吗???喂饭式带你学好!!!
1.1 JDK 各版本主要特性回顾 JDK Version 1.019960123 Oak(橡树) 初代版本,伟大的一个里程碑,但是是纯解释运行,使用外挂JIT,性能比较差,运行速度慢。 JDK Version 1.119970219 JDBC(Java DataBase Connectivity); 支持内部类; RMI(Remote Me
阿里巴巴技术专家之作,吊打面试官系列!
美团 一面: 1、ConcurrentHashMap实现原理 2、HashMap实现原理 3、锁的实现原理 4、synchronized和重入所实现原理以及区别 5、一个char[]数组,里面有空格,以&结束。 6、jvm内存模型,都存什么。以及垃圾回收算法,垃圾回收器。 7、内存溢出的场景 8、设计模式,以及自己使用的场景。 9、Sping的AOP实现原
网安行业这几个熟悉又陌生的名词,啥帽子都清楚啦?
随着网络的普及,黑客、暗网、黑产,网络上不法分子越来越多。但现在从国家到每个人对于网络安全意识越发的重视,魔高一尺道高一丈,白帽、红帽的出现打击了不法分子嚣张的气焰,那么,这几个熟悉又陌生的名词你知道是啥意思么?下面小编带你一起来盘点一下。1、黑产网络黑产,指以互联网为媒介,以网络技术为主要手段,为计算机信息系统安全和网络空间管理秩序,甚至国家安全、社会政治
这些CTF,不仅学技术,还有巨额奖金!
前言:不会吧,不会吧,不会还有安全er不知道CTF是什么吧?哈哈,跟大家开个玩笑。金庸武侠小说中,武林高手要么举办华山论剑,要么召开武林大会,通过这些盛会和比赛来切磋武力值。在程序员的世界里,也有ACM这样的编程大赛,成为各路编程高手一较高下展示能力的平台。那在网络安全的圈子里,各路黑客红客白帽子们又是如何秀出他们的狂拽炫酷吊炸天的技术的呢?这就是本文的主题
大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet
一、TreeSet 概述 1、TreeSet 是 SortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。 2、TreeSet顾名思义他内部维护的是一个TreeMap,底层是红黑二叉树,他使得集合内都是有序的序列。   3、Tree 可以按照添加对象的指定属性,进行排序,所以向TreeSet中添加的数据,要求是相同类的对象。 4、两
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo

热门文章

数据库系统概论操作系统List集合计算机网络大数据排序

最新文章

数据库系统概论List集合计算机网络Java的其他Map双指针问题