开发者社区> 游客gsugatesykzaq> 正文

Java容器 --- ConcurrentHashMap分析

简介: Java容器 --- ConcurrentHashMap分析
+关注继续查看

ConcurrentHashMap 引出


HashMap在多线程环境下存在线程安全问题,一般的解决方案:


  • 使用Collections.synchronizedMap(Map):创建线程安全的map集合;ps:在SynchronizedMap内部维护了一个普通对象Map,还有排斥锁mutex。最终结果是map的所有方法都上锁。该方法是Collections类中的静态方法,返回的是一个线程安全的HashMap
  • Hashtable:HashTable和HashMap一样都实现了Map接口,但是HashTable是一个线程安全的类。在HashTable中,使用的是同一个锁,所以当一个线程操作某一个功能时,其他线程想要操作另外的功能就要等待锁被让出来,比如get方法。
  • ConcurrentHashMap:concurrentHashMap采用了【锁分段】技术,不同的地方使用了不同的锁,功能之间的锁不一样,操作不同功能时就不再需要等待,这样就大大提高了执行效率。


ps:Hashtable与ConcurrentHashMap的区别


image.png

hashtable全表锁

image.png

jdk1.7分段锁

image.png

jdk1.8锁定Node节点(CAS + synchronized实现)


ConcurrentHashMap 的实现原理是什么?


底层数据结构和HashMap jdk1.7和jdk1.8基本一致(查询时间复杂度不同)。

多线程并发问题:


  • put数据丢失(被覆盖)
  • resize时导致循环链表问题,调用get方法死循环


ConcurrentHashMap 在 JDK1.7 和 JDK1.8 解决并发安全问题(安全机制:粒度不同)


  • jdk7采用分段锁+ReentrantLock。每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。
  • JDK1.8 的时候已经摒弃了 Segment 的概念,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化)


拓展:CAS是什么?自旋又是什么?


  • CAS 是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的。
  • CAS 操作:线程在读取数据时不进行加锁,在准备写回数据时,比较原值是否修改,若未被其他线程修改则写回,若已被修改,则重新执行读取流程。
  • 存在ABA问题:版本号机制 / 时间戳解决。

JDK1.8 中为什么使用内置锁 synchronized替换 可重入锁 ReentrantLock?

  • 在 JDK1.6 中,对 synchronized 锁的实现引入了大量的优化,并且 synchronized 有多种锁状态,会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
  • 减少内存开销 。假设使用可重入锁来获得同步支持,那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的,只有链表的头节点(红黑树的根节点)需要同步,这无疑带来了巨大内存浪费。


拓展:什么是可重入锁?有哪些?


  • 广义上的可重入锁指的是可重复可递归调用的锁,在外层使用锁之后,在内层仍然可以使用,并且不发生死锁(前提得是同一个对象或者class),这样的锁就叫做可重入锁。ReentrantLock和synchronized都是可重入锁。但是,ReentrantLock 和 synchronized 不一样,需要手动释放锁,所以使用 ReentrantLock的时候一定要手动释放锁,并且加锁次数和释放次数要一样(不然会死锁)。ps:一般而言,可重入的函数一定是线程安全的,反之则不一定成立。


拓展:synchronized的可重入怎么实现?


  • 每个锁关联一个线程持有者和一个计数器。当计数器为0时表示该锁没有被任何线程持有,那么任何线程都都可能获得该锁而调用相应方法。当一个线程请求成功后,JVM会记下持有锁的线程,并将计数器计为1。此时其他线程请求该锁,则必须等待。而该持有锁的线程如果再次请求这个锁,就可以再次拿到这个锁,同时计数器会递增。当线程退出一个synchronized方法/块时,计数器会递减,如果计数器为0则释放该锁。


拓展:ReentrantLock还可以实现公平锁机制。什么叫公平锁呢?也就是在锁上等待时间最长的线程将获得锁的使用权。通俗的理解就是谁排队时间最长谁先执行获取锁。


ConcurrentHashMap 的 put 方法执行逻辑是什么?


jdk1.7:


  • 先定位到相应的 Segment ,然后再进行 put 操作。
  • 首先会尝试获取锁,如果获取失败肯定就有其他线程存在竞争,则利用 scanAndLockForPut() 自旋获取锁。
    • 尝试自旋获取锁。
    • 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取,保证能获取成功。


jdk1.8:


  • 根据 key 计算出 hash 值;
  • 判断是否需要进行初始化;
  • 定位到 Node,拿到首节点 f,判断首节点 f:
    • 如果为 null ,则通过 CAS 的方式尝试添加;
    • 如果为 f.hash = MOVED = -1 ,说明其他线程在扩容,参与一起扩容;
    • 如果都不满足 ,synchronized 锁住 f 节点,判断是链表还是红黑树,遍历插入;
  • 当在链表长度达到 8 的时候,数组扩容或者将链表转换为红黑树。


ConcurrentHashMap 的 get 方法执行逻辑是什么?


jdk1.7:


  • 首先,根据 key 计算出 hash 值定位到具体的 Segment ;
  • 再根据 hash 值获取定位 HashEntry 对象
  • 并对 HashEntry 对象进行链表遍历,找到对应元素。


由于 HashEntry 涉及到的共享变量都使用 volatile 修饰,volatile 可以保证内存可见性,所以每次获取时都是最新值。


jdk1.8:


  • 根据 key 计算出 hash 值,判断数组是否为空;
  • 如果是首节点,就直接返回;
  • 如果是红黑树结构,就从红黑树里面查询;
  • 如果是链表结构,循环遍历判断。


ConcurrentHashMap 的 get 方法是否要加锁,为什么?


get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的,在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。


这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 效率高的原因之一。


image.png

拓展:get 方法不需要加锁与 volatile 修饰的哈希桶数组有关吗?


没有关系。哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。


image.png

拓展:volatile


  • 保证了不同线程对这个变量进行操作时的可见性,即一个线程修改了某个变量的值,这新值对其他线程来说是立即可见的。
  • 禁止进行指令重排序。
  • volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。


为什么Hashtable, ConcurrentHashMap 的 key和value 不能为null(并发角度分析)


ConcurrentHashmap和Hashtable都是支持并发的,二者规定key,value均不能为null,null的话,会抛出空指针异常。


  • 当通过get(k)获取对应的value时,如果获取到的是null时,无法判断,它是put(k,v)的时候value为null,还是这个key从来没有做过映射,出现歧义。假如线程1调用m.contains(key)返回true,然后在调用m.get(key),这时的m可能已经不同了。因为线程2可能在线程1调用m.contains(key)时,删除了key节点,这样就会导致线程1得到的结果不明确,产生多线程安全问题,因此,Hashtable和ConcurrentHashMap的value不能为null。
  • key不能为空,因为采用了fail-safe机制,这种机制会使得读取的数据不一定是最新的,使用null值,就会使得其无法判断对应的key是不存在还是为空,因为你无法再调用一次contain(key)来对key是否存在进行判断,HashTable同理。故在入参时,若为 null 就报空指针异常,而且在取hashcode时,压根就没考虑空的情况


HashMap允许key和value为null,在单线程时,调用contains()和get()不会出现问题,但是多线程下,就是线程不安全的。如果要保证线程安全,应该使用ConcurrentHashMap 。


快速失败(fail—fast)


快速失败(fail—fast)是java集合中的一种机制, 在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。


  • 迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount 变量。
  • 集合在被遍历期间如果内容发生变化,就会改变modCount的值。
  • 每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。


Tip:这里异常的抛出条件是检测到 modCount!= expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的bug。


java.util包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)算是一种安全机制吧。


拓展:安全失败(fail—safe)大家也可以了解下,java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。


ConcurrentHashMap 的并发度是什么?


  • 并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中,实际上就是ConcurrentHashMap中的分段锁个数,即Segment[]的数组长度,默认是16,这个值可以在构造函数中设置。
  • 如果自己设置了并发度,ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度,也就是比如你设置的值是17,那么实际并发度是32。
  • 如果并发度设置的过小,会带来严重的锁竞争问题;如果并发度设置的过大,原本位于同一个Segment内的访问会扩散到不同的Segment中,CPU cache命中率会下降,从而引起程序性能下降。
  • 在JDK1.8中,已经摒弃了Segment的概念,选择了Node数组+链表+红黑树结构,并发度大小依赖于数组的大小。


ConcurrentHashMap 迭代器是强一致性还是弱一致性?


  • 与 HashMap 迭代器是强一致性不同,ConcurrentHashMap 迭代器是弱一致性。
  • ConcurrentHashMap 的迭代器创建后,就会按照哈希表结构遍历每个元素,但在遍历过程中,内部元素可能会发生变化,如果变化发生在已遍历过的部分,迭代器就不会反映出来,而如果变化发生在未遍历过的部分,迭代器就会发现并反映出来,这就是弱一致性。
  • 这样迭代器线程可以使用原来老的数据,而写线程也可以并发的完成改变,更重要的,这保证了多个线程并发执行的连续性和扩展性,是性能提升的关键。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的,?mysql的 3306,?mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建. ? have?fun! ?将编程看作是一门艺术,而不单单是个技术。
20110 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22248 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23538 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36365 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14697 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13070 0
150
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载
http://www.vxiaotou.com