HashMap
Map是我们在集合中非常重要的一个集合、我们刚学习HashMap的时候就说它不安全、可是不知道不安全会发生什么后果
我们先来看看JDK7和JDK8当中的HashMap有什么不一样
JDK7 HashMap链表循环造成死循环
造成HasMap链表循环列表的原因就是因为在hash冲突的时候采用了头插法且没有加锁的方式插入链表、在HashMap put的时候,put函数会检查元素是否超出了阈值【数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定)】,如果超出了数组长度扩容为两倍,下面是它扩容时将旧hash表转到新hash表从而完成扩容的源代码
/** * 作用:将旧数组上的数据(键值对)转移到新table中,从而完成扩容 * 过程:按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后,链表逆序 */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //通过遍历 旧数组,将旧数组上的数据(键值对)转移到新数组中 for (Entry
在单线程中,这样的代码是没有什么问题,问题就是有很多个线程,我们假设有两个线程t1和t2,他们都执行到Entry
编辑切换为居中
添加图片注释,不超过 140 字(可选)
,t1的时间片已经用完了,t2还在继续执行,此时t1、t2获取的e和next分别为e1、e2、next1、next2,再之后t2完成了扩容操作,链表顺序已经从原来的abcd变成了dcba,t1线程的e在next的上方,如下图示:
编辑切换为居中
添加图片注释,不超过 140 字(可选)
此时t1线程醒过来了,继续执行就会出现链表循环,造成while死循环
编辑切换为居中
添加图片注释,不超过 140 字(可选)
JDK8 HashMap中已经采用尾插法进行插入避免了链表循环、且链表长度大于8会变成红黑树
HashMap数据丢失
jdk7:hashMap put的时候有hash冲突如果没有超过阈值,就会采用头插法来插入链表,假如有t1和t2线程,它们都同时获得了,链表的头节点,此时t1线程的时间片没有了,t2线程还在继续,t2线程已经执行完了put操作,t1线程醒过来,t1线程会将自己的下一个节点指向头节点,这样刚刚t2线程put的节点就丢失了
jdk8: 采用的是尾插法、一样的两个线程都同时获取了尾节点、后执行的那个线程会覆盖掉前一个线程的节点、造成丢失
HashMap在官方的设定的就是线程不安全的,要安全选ConcurrentHashMap
JDK7 ConcurrentHashMap
在jdk7 ConcurrentHashMap当中采用了一个分段锁的方式(Segment[])来保证线程安全
编辑切换为居中
添加图片注释,不超过 140 字(可选)
Segment类继承了ReentrantLock,Segment类里有多个槽。
put:
计算出key在那个Segment,然后上锁,再算出在哪个槽里,此时如果有其它线程访问这个Segment会被阻塞住,直到unlock。
get:
CAS + volatile
在HashTable当中是锁住了整个对象,线程t1 get("key1") 、线程t2 put("key2", "value2"),线程t2也会被阻塞住,在ConcurrentHashMap中这两个操作是不会阻塞且不受影响。
值得注意的是Segment[]的初始长度,默认是16,不会因为数据的多少而改变,所以默认最多只有16个线程获得锁,这个初始值可以设置,但是需要我们自己去评估多少合适。
Segment分段锁实现下的ConcurrentHashMap的劣势:
寻找元素需要经过两次hash
并发级别(Segment[]长度)的合理设置问题。虽然提供了默认的并发级别,但是是否在大多数场景下都适用?归根结底,就是需要用户自己来评估需要多少把锁来分段治理的问题。
在存储成本比HashMap高。每个Segment管理的最少容量是2,而默认的并发级别为16,即16个Segment。假如我只需要存储的是16个元素,那么ConcurrentHashMap会需要占用2倍的存储空间。
JDK8 ConcurrentHashMap
在JDK8中,ConcurrentHashMap采用更加细粒度的锁取消分段锁,synchronized + CAS
put:
如果发现该槽没有数据,初始化头节点时,ConcurrentHashMap并没有加锁,而是CAS的方式进行原子替换(原子操作,基于Unsafe类的原子操作API) 如果发现该槽有数据,判断是否正在扩容,如果是则会去帮助扩容,扩容时会进行加锁处理,锁定是头节点。 如果发现该槽有节点且不在扩容,则会去锁(synchronized)住该槽的头节点,进行插入
get:
没有什么加锁的操作,hash表被volatile修饰
原文链接: https://www.cnblogs.com/isyuesen/p/16693208.html