系统化的学习技术、研究技术而不是使用技术

集合框架笔记--ConcurrentHashMap

2018/10/24 17:09:18 | 浏览(7) Java技术

一、前言

HashMap在put元素的时候,如果插入的元素超过了负载因子的范围时,就会触发扩容操作,也就是rehash,这个情况下会将原数据重新hash到新的数组中。在多线程环境下,存在同时有其他线程在进行put操作,如果hash值相同,就可能就会导致链表产生闭环,从而在get操作时造成死循环,所以说HashMap是非线程安全的

Hashtable是JDK1.0就存在的map类,它是线程安全的,实现原理是在所有涉及多线程的操作上加上了synchronrized关键字来锁住整个map,所有的多线程操作都在竞争同一把锁,自然效率是低下的。

在JDK1.5版本的时候,引入了java.util.concurrent包,这个包提供了一系列让并发编程变得更容易的类。其中就包括本篇笔记所提到的类ConcurrentHashMap。它是线程安全的,但是它在JDK1.7和JDK1.8版本的实现却不一样。

二、基于分段锁的实现(JDK1.7)

锁分段技术 将容器中的数据按一段一段的存储,每一段数据分配一把锁,这样当一个线程访问某段中的数据时,其他段的数据还可以被其他线程访问,容器的性能自然也大大提升。

在JDK1.7版本中,ConcurrentHashMap由一个Segment数组和多个HashEntry组成。Segment继承了可重入锁ReentrantLock,扮演着锁的角色,同时它的结构与HashMap类似,是一种数组+链表的结构,一个Segment中包含一个HashEntry数组,HashEntry是一个链表结构的元素,每个Seqment守护着它里边的HashEntry元素,任何线程想要进行修改时必须获得Segment锁。

但是,这个方案也并不是完美的。当需要进行跨段操作的时候(也就是需要获得全局锁的时候),就比较麻烦了,需要获得所有分段的锁才能获取到全局信息。比如size()方法。换言之ConcurrentHashMap的分段数也就代表了它的最大并发能力。

三、基于CAS的实现(JDK1.8)

关键词:CAS、volatile、synchronrized

JDK1.8为进一步提高并发性,摒弃了分段锁的方案,而是直接使用一个大的数组。同时为了提高哈希冲突情况下的寻址性能,在链表长度超过阈值(8)的时候将链表自动转换为红黑树。

对于put操作,流程如下:

  1. 若Key对应的数组元素(链表头或树的根元素)为null时,使用CAS操作将其设为新值;
  2. 若不为空,则对该元素使用synchronrized关键字申请锁,并进行put操作;
  3. 最后判断链表的长度若超过阈值则转换为红黑树;

对于读操作,由于数组被volatile修饰,保证了table的可见性。另外每个元素又是一个Node实例,它的key值 、hash值有final关键字,数据确定不会被更改,而val值和next值都有volatile修饰,可见性同样也有保证。

对于size操作,大的数组每个都有维护一个计数器,put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。

需要注意的是,之所以在每个数组中包含一个计数器,而不是在 ConcurrentHashMap 中使用全局的计数器,是对ConcurrentHashMap并发性的考虑:因为这样当需要更新计数器时,不用锁定整个ConcurrentHashMap。另外,count是volatile的,这使得对count的任何更新对其它线程都是立即可见的。

参考文章

留言(0)

给我留言