浅谈HashMap在高并发下的问题
前言
总所周知，HashMap不是线程安全的，在高并发情况下会出现问题。特别是，在java1.7中，多线程的HashMap会出现CPU 100%的严重问题。这个问题是怎样产生的，后续版本还会有这个问题吗（指java8及后续版本）？下面就来用通俗的语言讲解下。
解析
关于这个问题，是由于java7多线程扩容机制下链表变为循环链表，再获取该链表导致的。
看下java7中扩容的代码。java7中HashMap的实现为数组+链表的形式，没有红黑树。
java7扩容的原则很简单，新数组长度为原数组2倍。遍历原数组，将数组每个位置（有可能为空，有可能只有一个数组，有可能是一个链表）重新哈希，放到对应的新数组上。全部遍历完后更改数组指针，指向新数组。需要注意的是，这里重哈希将链表元素放到新数组，使用的是头插法。
// 扩容核心方法，基本思想就是遍历数据，使用头插法将旧数组元素移到新数组。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历旧数组
for (Entry<K,V> e : table) {
// 元素不为空。遍历该位置链表
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 头插法,新节点next指向该位置首节点
newTable[i] = e; // 新元素归位
e = next; // 指向下一个节点，继续遍历
}
}
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity]; // 创建新数组
transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 扩容
table = newTable; // 更改指针
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
这里处理的话，如果单线程情况下不会有问题。如果在多线程情况下，会导致链表在扩容过程中形成循环链表。
形成循环链表的原因在于多线程和头插法。试想，两个线程在添加元素时，同时发现该扩容了，然后同时发起扩容过程。由上述代码可知，扩容完成之前是在自己的线程里创建一个新数组。等扩容完成后（也就是将原数组元素迁移到新数组后）再更改指针指向新扩容数组。
举例初始HashMap是这样的
假设两个线程同时扩容，一个线程扩容到一半后被挂起。（标识了某链表的e和next）,另一个线程执行扩容，且完成了扩容。
红色的数组和元素表示线程1，也就是扩容一半挂起的线程，而线程二已完成扩容。观察完成扩容的线程二，在3的位置，该链表的位置顺序已经改变（原数组顺讯为3->7,现在反过来了，这是使用头插法的效果，你也可以对着代码试试）。从图中也可以看出，线程1，2分别创建了自己的新数组，并在自己的新数组中完成扩容。
这时线程1开始执行。熟悉下它即将执行的代码。
// transfer 方法循环部分
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 头插法,新节点next指向该位置首节点
newTable[i] = e; // 新元素归位
e = next; // 指向下一个节点，继续遍历
}
下面线程1将使用头插法将元素插入线程1新建的数组中去。注意此时e指向的是Key3,next指向的是Key7。不用想也知道后面操作会有问题。因为现在的next指针指的不是e的下一个元素，而是它的前一个元素！
如果继续走代码的话，把Key3(当前e指向元素)放入新数组后，再把Key7放入新数组，后面会放哪个元素？当然又是Key3了，因为Key7next是Key3,这样就形成了死循环。
java8的改进
- 添加了红黑树，当链表长度大于8时，会将链表转为红黑树。
- 扩容后，新数组中的链表顺序依然与旧数组中的链表顺序保持一致。具体JDK8是用 head 和 tail 来保证链表的顺序和之前一样，这样就不会产生循环引用。也就没有死循环了。
- 虽然修复了死循环的BUG，但是HashMap 还是非线程安全类，仍然会产生数据丢失等问题。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。
相关推荐
-
关于HashMap 并发时会引起死循环的问题解析
今天研读Java并发容器和框架时,看到为什么要使用ConcurrentHashMap时,其中有一个原因是:线程不安全的HashMap, HashMap在并发执行put操作时会引起死循环,是因为多线程会导致HashMap的Entry链表形成环形数据结构,查找时会陷入死循环. 纠起原因看了其他的博客,都比较抽象,所以这里以图形的方式展示一下,希望支持! 1)当往HashMap中添加元素时,会引起HashMap容器的扩容,原理不再解释,直接附源代码,如下: /** * * 往表中添加元素,如果插入元素
-
深入学习java并发包ConcurrentHashMap源码
正文 以前写过介绍HashMap的文章,文中提到过HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的. JDK1.7的实现 整个 ConcurrentHashMap 由一个个 Segment 组成,Seg
-
基于Java并发容器ConcurrentHashMap#put方法解析
jdk1.7.0_79 HashMap可以说是每个Java程序员用的最多的数据结构之一了,无处不见它的身影.关于HashMap,通常也能说出它不是线程安全的.这篇文章要提到的是在多线程并发环境下的HashMap--ConcurrentHashMap,显然它必然是线程安全的,同样我们不可避免的要讨论散列表,以及它是如何实现线程安全的,它的效率又是怎样的,因为对于映射容器还有一个Hashtable也是线程安全的但它似乎只出现在笔试.面试题里,在现实编码中它已经基本被遗弃. 关于HashMap的线程不
-
Java并发编程之详解ConcurrentHashMap类
前言 由于Java程序员常用的HashMap的操作方法不是同步的,所以在多线程环境下会导致存取操作数据不一致的问题,Map接口的另一个实现类Hashtable 虽然是线程安全的,但是在多线程下执行效率很低.为了解决这个问题,在java 1.5版本中引入了线程安全的集合类ConcurrentMap. java.util.concurrent.ConcurrentMap接口是Java集合类框架提供的线程安全的map,这意味着多线程同时访问它,不会影响map中每一条数据的一致性.ConcurrentM
-
Java并发系列之ConcurrentHashMap源码分析
我们知道哈希表是一种非常高效的数据结构,设计优良的哈希函数可以使其上的增删改查操作达到O(1)级别.Java为我们提供了一个现成的哈希结构,那就是HashMap类,在前面的文章中我曾经介绍过HashMap类,知道它的所有方法都未进行同步,因此在多线程环境中是不安全的.为此,Java为我们提供了另外一个HashTable类,它对于多线程同步的处理非常简单粗暴,那就是在HashMap的基础上对其所有方法都使用synchronized关键字进行加锁.这种方法虽然简单,但导致了一个问题,那就是在同一时间
-
Java HashMap源码及并发环境常见问题解决
HashMap源码简单分析: 1 一切需要从HashMap属性字段说起: /** The default initial capacity - MUST be a power of two. 初始容量 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by eit
-
浅谈HashMap在高并发下的问题
前言 总所周知,HashMap不是线程安全的,在高并发情况下会出现问题.特别是,在java1.7中,多线程的HashMap会出现CPU 100%的严重问题.这个问题是怎样产生的,后续版本还会有这个问题吗(指java8及后续版本)?下面就来用通俗的语言讲解下. 解析 关于这个问题,是由于java7多线程扩容机制下链表变为循环链表,再获取该链表导致的. 看下java7中扩容的代码.java7中HashMap的实现为数组+链表的形式,没有红黑树. java7扩容的原则很简单,新数组长度为原数组2倍.遍
-
浅谈HashMap中7种遍历方式的性能分析
目录 一.前言 二.HashMap遍历 2.1.迭代器EntrySet 2.2.迭代器 KeySet 2.3.ForEachEntrySet 2.4.ForEach KeySet 2.5.Lambda 2.6.Streams API 单线程 2.7.Streams API 多线程 三.性能分析 四.字节码分析 五.EntrySet性能分析 六.安全性测试 6.1.迭代器方式 6.2.For 循环方式 6.3.Lambda 方式 6.4.Stream 方式 6.5.小结 七.总结 一.前言 随着
-
浅谈HashMap、HashTable的key和value是否可为null
结论: HashMap对象的key.value值均可为null. HahTable对象的key.value值均不可为null. 且两者的的key值均不能重复,若添加key相同的键值对,后面的value会自动覆盖前面的value,但不会报错. public class Test { public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>();//Has
-
浅谈hashmap为什么查询时间复杂度为O(1)
hashmap为什么查询时间复杂度为O(1) Hashmap是java里面一种类字典式数据结构类,能达到O(1)级别的查询复杂度,那么到底是什么保证了这一特性呢,这个就要从hashmap的底层存储结构说起 下来看一张图: 上面就是hashmap的底层存储示意图,要想查看一个键值对应的值,首先根据该键值的hash值找到该键的hash桶位置,即是tab[2]还是tab[1]等,计算某个键对应的哈希桶位置很简单,就是 int pos = (n - 1) & hash,也就是hash%n,因为位运算效率
-
浅谈python之高阶函数和匿名函数
map() map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每个元素,并把结果作为新的Iterator返回. def func(x): return x*x r = map(func, [1, 2, 3, 4, 5]) print(type(r)) r = list(r) print(r) 输出结果: <class 'map'> [1, 4, 9, 16, 25] 可以看出,map让函数func作用于列表的每一项,使列表的每一项都被函数func
-
浅谈C++高并发场景下读多写少的优化方案
目录 概述 分析 双缓冲 工程实现上需要攻克的难点 核心代码实现 简单说说golang中双缓冲的实现 相关文献 概述 一谈到高并发的优化方案,往往能想到模块水平拆分.数据库读写分离.分库分表,加缓存.加mq等,这些都是从系统架构上解决.单模块作为系统的组成单元,其性能好坏也能很大的影响整体性能,本文从单模块下读多写少的场景出发,探讨其解决方案,以其更好的实现高并发.不同的业务场景,读和写的频率各有侧重,有两种常见的业务场景: 读多写少:典型场景如广告检索端.白名单更新维护.loadbalance
-
浅谈jquery拼接字符串效率比较高的方法
实例如下: var roleidArray = new Array(""); for(i = 0; i < rightRows.length; i++) { roleidArray.push(rightRows[i].id); } roleidArray = roleidArray.join(",").substring(1); 代码很简单,我就不做注释了 以上这篇浅谈jquery拼接字符串效率比较高的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,
-
浅谈Mybatis中resultType为hashmap的情况
现在有一张user表 id ,name,age 我们进行一个简单的查询: <select id="test" resultType="Uer"> select id ,name,age from user </select> 查询完后,怎么去接收这个查询结果呢,通常在这个mapper.xml对应的接口中使用List<User>做为返回值去接收,最后存储的样子就是下面的图 这是一个很简单的单表查询操作,其实这种简单的单表查询操作不需
-
浅谈java中HashMap键的比较方式
先看一个例子 Integer integer=12344; Integer integer1=12344; 在Java中Integer 和Integer1是不相等的,但是如果再执行如下语句 map.put(integer, 1); map.put(integer1, 2); 会发现2会把1覆盖,问题来了,明明是两个不同的对象,为什么,2会把1覆盖呢? 我们看HashMap中添加键的源代码,如下 可以发现我们传进来的键交给了一个hash的成员方法区处理,这里我们看看hash方法的源码 哦,看到这里
-
浅谈Redis哨兵模式高可用解决方案
目录 一.序言 1.目标与收获 2.端口规划 二.单机模拟 (一)服务规划 1.Redis实例 2.哨兵服务 (二)服务配置 1.Redis实例 2.哨兵服务 (三)服务管理 1.Redis实例 2.哨兵服务 三.客户端整合 (一)基础整合 1.全局配置文件 2.集成配置 (二)读写分离 一.序言 Redis高可用有两种模式:哨兵模式和集群模式,本文基于哨兵模式搭建一主两从三哨兵Redis高可用服务. 1.目标与收获 一主两从三哨兵Redis服务,基本能够满足中小型项目的高可用要求,使用Supe