为什么HashMap线程不安全?以及实现HashMap线程安全的解决方案 |
您所在的位置:网站首页 › 双面镜为什么不安全呢 › 为什么HashMap线程不安全?以及实现HashMap线程安全的解决方案 |
一、为什么HashMap线程不安全?
原著参考 1、JDK1.7 扩容引发的死循环和数据丢失(1).当前jdk1.7版本的HashMap线程不安全主要是发生在扩容函数中,其中调用了HshMap的transfer()方法 //jdk 1.7的transfer方法,HashMap的扩容操作 void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }在执行数组扩容操作时,数据会重新定位新数组中索引,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是形成死循环的关键点。如何造成死循环以及数据丢失的。 (2)、数组扩容时如何造成死循环和数据丢失? 我们假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作:
(1)dk1.7的数据丢失、死循环问题在JDK1.8中已经得到了很好的解决,直接在HashMap的resize()中完成了数据迁移。 (2)为什么说 JDK1.8会出现数据覆盖的情况? 查看这段JDK1.8中的put操作代码: 不建议使用HashTable,Oracle官方也将其废弃,建议在多线程环境下使用ConcurrentHashMap类。 (1)Hashtable的操作 HashTable的操作几乎和HashMap一致,主要的区别在于HashTable为了实现多线程安全,在几乎所有的方法上都加上了synchronized锁(锁的是类的实例,也就是整个map结构),当一个线程访问 Hashtable 的同步方法时,其他线程如果也要访问同步方法,会被阻塞住。举个例子,当一个线程使用 put 方法时,另一个线程不但不可以使用 put 方法,连 get 方法都不可以,而加锁的结果就是HashTable操作的效率十分低下。 (2)HashTable与HashMap对比 ①线程安全 HashMap是线程不安全的类,多线程下会造成并发冲突,但单线程下运行效率较高; HashTable是线程安全的类,很多方法都是用synchronized修饰,但同时因为加锁导致并发效率低下,单线程环境效率也十分低; ②插入null HashMap最多允许有一个键为null,允许多个值为null; HashTable不允许键或值为null; ③容量 HashMap底层数组长度必须为2的幂(16,32,128…),这样做是为了hash准备,默认为16; HashTable底层数组长度可以为任意值,这就造成了hash算法散射不均匀,容易造成hash冲突,默认为11; ④Hash映射 HashMap的hash算法通过非常规设计,将底层table长度设计为2的幂,使用位与运算代替取模运算,减少运算消耗; // HashMap static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 下标index运算 int index = (table.length - 1) & hash(key)HashTable的hash算法首先使得hash值小于整型数最大值,再通过取模进行散射运算; // HashTable int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;⑤扩容机制 HashMap创建一个为原先2倍的数组,然后对原数组进行遍历以及rehash(再次求桶); HashTable扩容将创建一个原长度2倍的数组,再使用头插法将链表进行反序; ⑥结构区别 HashMap是由数组+链表形成,在JDK1.8之后链表长度大于8时转化为红黑树; HashTable一直都是数组+链表; ⑦继承关系 HashTable继承自Dictionary类; HashMap继承自AbstractMap类; ⑧迭代器 HashMap的 Iterator 迭代器是fail-fast; fail-fast(快速失败机制):当我们在遍历集合元素的时候,经常会使用迭代器,但在迭代器遍历元素的过程中,如果集合的结构被修改(增加、删除),就会抛出Concurrent Modification Exception(并发修改异常),防止继续遍历。 fail-safe(安全失败机制):当集合的结构被改变的时候,fail-safe机制会在复制原集合的一份数据出来,然后在复制的那份数据遍历。因此,fail-safe不会抛出异常,但存在以下缺点:①复制时需要额外的空间和时间上的开销。②不能保证遍历的是最新内容。 HashTable的 Enumerator不是。 2.Collections.synchronizedMap(一般不用)通过Collections.synchronizedMap()返回一个新的Map的实现 Map map = Collections.synchronizedMap(new HashMap());我们在调用上面这个方法的时候就需要传入一个Map,如下图可以看到有两个构造器,如果你传入了mutex参数,则将对象排斥锁赋值为传入的对象。 如果没有,则将对象排斥锁赋值为this,即调用synchronizedMap的对象,就是上面的Map 通过Collections.synchronizedMap()来封装所有不安全的HashMap的方法。 优点:代码实现十分简单,一看就懂 缺点:从锁的角度来看,基本上是锁住了尽可能大的代码块.性能会比较差. 3.ConcurrentHashMap(常用)(1)JDK 1.7 中,采用分段锁的机制,实现并发的更新操作,底层采用数组+链表的存储结构,包括两个核心静态内部类 Segment 和 HashEntry。 ①、Segment 继承 ReentrantLock(重入锁) 用来充当锁的角色,每个 Segment 对象守护每个散列映射表的若干个桶; ②、HashEntry 用来封装映射表的键-值对; ③、每个桶是由若干个 HashEntry 对象链接起来的链表
jdk 1.7源码分析 ConcurrentHashMap继承了AbstractMap类,并且实现了ConcurrentMap接口,并且线程安全的实现了接口中的增删改查的方法 get 方法的逻辑,需要将 Key 通过 Hash 之后定位到具体的 Segment ,再通过一次 Hash 定位到具体的元素上 由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的,保证了内存可见性,所以每次获取时都是最新值。 缺点:jdk1.7版本虽然可以支持每个Segment并发访问,但是基本上还是数组加链表的方式,当执行查询的时候,还得遍历链表,会导致效率很低. (2)JDK 1.8中抛弃了原有的 Segment 分段锁,来保证采用Node + CAS + Synchronized来保证并发安全性。取消类 Segment,直接用table 数组存储键值对;当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时,链表转换为红黑树,提升性能。底层变更为数组 + 链表 + 红黑树。 首先Node代替了1.7之中的HashEntry,并在val和next添加了volatile,保证了原子的可见性,也引入了红黑树,在链表大于一定值的时候会转换(默认是8)。 CAS性能很高,但synchronized之前一直都是重量级的锁,jdk1.8 引入了synchronized,采用锁升级的方式。 针对 synchronized 获取锁的方式,JVM 使用了锁升级的优化方式,就是先使用偏向锁优先同一线程然后再次获取锁,如果失败,就升级为 CAS 轻量级锁,如果失败就会短暂自旋,防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。 偏向锁:为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行,始终只有一个线程在执行同步块,在它没有执行完释放锁之前,没有其它线程去执行同步。 轻量级锁:当有两个线程,竞争的时候就会升级为轻量级锁。引入轻量级锁的主要目的是在没有多线程竞争的前提下,减少传统的重量级锁使用操作系统互斥量产生的性能消耗。 重量级锁:大多数情况下,在同一时间点,常常有多个线程竞争同一把锁,悲观锁的方式,竞争失败的线程会不停的在阻塞及被唤醒态之间切换,代价比较大 ConcurrentHashMap的get方法 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |