一、前言
本文紧接:HashMap线程不安全实例(jdk1.7) - seeAll - 博客园 (cnblogs.com),介绍jdk8中线程不安全的一些情况,且主要是在上篇文章的基础上和jdk1.7做一个对比。
二、初始化桶数组的例子
1,测试代码
和上篇文章一样。
2,断点设置
同样设置在初始化桶数组的地方,且断点的详细配置也和上篇文章一样,如下图
3,测试步骤
和上篇文章一样。
线程0和线程1都走到断点处;
线程0完成初始化动作,初始化了桶数组,并在数组中插入了第一个元素;
线程1在此之之后进行初始化动作。
4,结果分析
并没有出现,线程1的操作覆盖线程0的情况。
jdk1.7有这种情况,是因为初始化的方法,直接new一个新的空数组对象,赋值给了HashMap的桶数组,如下图所示
jdk8中没有这种情况,是因为初始化的方法中,虽然也是直接new一个新的空数组对象,赋值给了HashMap的桶数组,但是先前却持有了HashMap老数组的对象。这样其他线程的操作情况,都能通过这个老数组得知,并作出反应,避免了相互覆盖的情况,如下图
5,其他线程不安全情况
5.1,桶位插入第一个元素的情况
HashMap的桶数组的某个桶位插入第一个元素的时候,直接在桶位上new一个链表,和jdk1.7中初始化桶数组的情况类似,不管其他线程在该桶位上插入了多少元素了,当前线程只要停在此处并步进一步就会初始化该桶位上的链表。
5.2,桶位链表尾部链接新元素的情况
HashMap的桶数组的某个桶位链表链接新元素时,先循环链表以找到尾部元素,当两个线程同时找到尾部元素时,同时为其链接下个元素,会发生互相覆盖的问题。
6,其他说明
a,HashMap中元素的hash值和桶数组下标(桶位)的算法,在jdk1.7和jdk8中不同;所以如果要构造相同桶位的key,需要分别设计;比如在jdk1.7中,容量为16,key=1、16、35、50的元素会落在一个桶位;在jdk8中,相同的容量,key=1、17、33、49的元素会落在一个桶位。
b,HashMap中链表的元素插入方式,在jdk1.7和jdk8中不同;在jdk1.7中,使用“头插法”,即新元素放在链表的最前面;在jdk8中,新元素放在链表的最后面,且在链表长度即将超过8时,且桶数组长度大于等于64时,转化为红黑树,树也会在扩容时因为元素数量小于等于6而又变成链表。
三、链表成环的例子
1,回忆jdk1.7的情况
a,在jdk1.7中,触发扩容后,之前某个桶位上的链表,比如"月“->"秋“->"花“->"春“->null,所有元素会按照前后顺序一个一个操作,转移到自己对应的新桶位上。
b,比如其中“秋”和“春”会转移到同一个新桶位,新桶位已有的链表为“大”->"梦“->null。
c,查看下图红框中的代码,会发现转移元素的时候,也是使用的头插法,即先是“秋”接上“大”->"梦“->null变成“秋”->“大”->"梦“->null,然后赋值给新桶位,即新桶位当前的链表是“秋”->“大”->"梦“->null。然后“春”接上“秋”->“大”->"梦“->null变成“春”->“秋”->“大”->"梦“->null,再赋值给新桶位,最终新桶位当前的链表是“春”->“秋”->“大”->"梦“->null。
d,参考上篇文章,一个线程在转移元素的时候还是秋在前,春在后;另一个线程已经都转移好了,变成了春在前,秋在后;再回到最开始的线程,此时的情形已经和它固有的设计背道而驰了。
打个比方,完成上篇文章中未完成的游戏
前言:
人1、人2、人3分别代表栈里面的e、next、newTable[i];
道具“秋”、道具“春”,道具“大”,道具“梦”,道具null分别代表堆里面的待转移的或者已在链表中的元素对象;
“秋”前面的钩子钩在了“春”后面的环上,“秋”->“春”;
“大”前面的钩子钩在了“梦”后面的环上,“大”->“梦”;“梦”前面的钩子钩在了“null”后面的环上,“梦”->null;即“大”->"梦“->null;
人1抓着“秋”;
开始游戏:
a1,人2看下人1手上的“秋”,顺着看下去,“秋”勾着“春”,所以人2抓住这个“春”;
此时局外人人4解开了秋的钩子,反而把“春”前面的钩子钩在了“秋”后面的环上,“春”->“秋”;
a2,人1将自己手上“秋”的钩子解开(此时已经被人4解开了),勾到了人3抓着的“大”上面;
a3,人3松开手,抓住人1手上的“秋”;
a4,人1松开手,抓住人2手上的“春”;
b1,人2看下人1手上的“春”,顺着看下去,“春”勾着“秋”,所以人2抓住这个“秋”;
b2,人1将自己手上“春”的钩子解开,勾到了人3抓着的“秋”上面;
b3,人3松开手,抓住人1手上的“春”;
b4,人1松开手,抓住人2手上的“秋”;
c1,人2看下人1手上的“秋”,顺着看下去,“秋”勾着“大”,所以人2抓住这个“大”;
c2,人1将自己手上“秋”的钩子解开,勾到了人3抓着的“春”上面;问题来了,“春”勾着“秋”,现在“秋”又勾着“春”,不就形成环了吗。
2,jdk8的情况
2.1,插入元素的情况
新元素找到对应桶位后,先遍历桶位上的链表,直到找到尾部元素,最后才会将新元素挂到“链表尾部元素”的后面,如下图;和jdk1.7的头插法相比多了“循环遍历找尾部元素”的步骤。
2,扩容转移元素的情况
示例代码
public class MyNode { public int key; public String value; public MyNode next; public MyNode(int key, String value, MyNode next) { this.key = key; this.value = value; this.next = next; } public static void main(String[] args) { // “花” -> “春” -> null MyNode e = new MyNode(1, "花", new MyNode(17, "春", null)); // 假设原数组长度为8 int oldCap = 8; // 假设链表在原数组下标为1的位置 int oldIndex = 1; // 假设扩容后,新数组长度16 MyNode[] newTab = new MyNode[16]; MyNode loHead = null, loTail = null; MyNode hiHead = null, hiTail = null; MyNode next; do { next = e.next; // 扩容后,链表上某些元素所在数组下标位置不变,还在1 if ((hash(e.key) & oldCap) == 0) { if (loTail == null) // 如果尾部指针还没有指向元素,说明该元素e是第一个元素(头部元素) loHead = e; else // 如果尾部指针已经指向了元素,说明该元素e不是第一个元素,需要挂到尾部指针指向的元素 loTail.next = e; // 将尾部指针指向当前元素,表示当前元素现在是链表上的最后一个元素 loTail = e; } else { // 扩容后,链表上某些元素需要转移到数组另外的位置上,HashMap通过巧妙的设计,需要改变位置的只会转移到同一个位置(1+8=)9 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { // 链表的最后一个元素后挂上null,到此链表完整形成 loTail.next = null; // 处理转移后位置不变的元素,桶位指向他们形成的链表的头部元素 newTab[oldIndex] = loHead; } if (hiTail != null) { hiTail.next = null; // 处理转移后位置改变的元素,新桶位指向他们形成的链表的头部元素 newTab[oldIndex + oldCap] = hiHead; } System.out.println(Arrays.asList(newTab)); } // 直接copy的源码,为jdk1.8中hashMap计算hash值的方法 public static int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } @Override public String toString() { return "MyNode{" + "key=" + key + ", value='" + value + '\'' + ", next=" + next + '}'; } }
运行结果
结果分析
使用固定”头部指针“,移动”尾部指针“的方式,实现正序;
假如使用固定”尾部指针“,移动”头部指针“的方式,也能实现倒序,改成下面代码替换进去;
if (loHead == null) loTail = e; else e.next = loHead; loHead = e;
之所以使用正序,先来的元素在前面,后来的元素在后面,和HashMap中put元素采用尾插法一样,应该是有原因的。可能是为了整体的一致性,防止出现jdk1.7中那种问题吧。
四、总结
1,
jdk1.7中,初始化桶数组时,会发生线程安全问题,两个线程同时走到初始化动作那一行,不管谁快谁慢,最终总有一方覆盖另一方;
jdk8中,初始化桶数组时,不会发生线程安全问题,不管谁,都会在初始化完后,继续将对方的操作结果与自己的操作结果进行融合。
2,
jdk8中,桶位链表初始化第一个元素时,会发生线程安全问题,原理同上jdk1.7初始化桶数组一样,两个线程走到初始化动作那一行,不管谁快谁慢,最终总有一方覆盖另一方;
3,
jdk1.7中,链表头插新元素时,会发生线程安全问题,因为桶位原先指向链表的头部对象,插入新元素后需要指向新元素对象,在堆里面是两个不同的对象;
线程执行方法,对应”虚拟机栈“,栈里有个变量(不管是局部变量,还是方法参数),变量指向堆里的桶位对象,这个变量一旦指定对象后,就不会重新指向了(除非代码里,下面有将这个变量指向另一个对象,需要一行代码,再换个对象,又需要一行代码,可是代码是早就写好的,不会动态的改变),无法保证变量指向的对象接下来使用前会不会过时。
可以理解为,在虚拟机层面,获取对象和使用对象是两个步骤,两个步骤之间一定有时间间隔,时间间隔内对象可能过时;
jdk8使用尾插法,桶位指向的一直是一个对象,就不会存在这样的问题;但是会出现其他问题,如下面
4,
在jdk8中,链表尾插新元素时,会发生线程安全问题,原理同上,线程执行方法对应的栈中的变量指向链表的尾部元素对象,但是这个尾部元素对象也会过时。
5,
jdk1.7中,扩容翻转链表时,会发生线程安全问题,因为HashMap插入元素和扩容转移元素都是使用头插法,相当于一个正面朝上的硬币,插入后变成反面朝上,扩容转移后又变成正面朝上;
两个线程同时扩容翻转链表时,一个线程正在处理正面朝上的硬币,它的思路就是按照正面朝上处理了,且已经处理了一半,中途被另一个线程把硬币变成了反面朝上,之前的线程的思路又不会转变,最终导致问题。
jdk8使用尾插法后,一个正面朝上的硬币,插入后还是正面朝上,扩容转移后还是正面朝上,一直不会改变,也就不会出现偏差和矛盾的地方,没有循环依赖的问题。
标签:HashMap,元素,next,链表,jdk8,线程,数组,null From: https://www.cnblogs.com/seeall/p/18065592