此时线程A中运行结果如下:
线程A挂起后,此时线程B正常执行,并完成resize操作,结果如下:
这里需要特别注意的点:由于线程B已经执行完毕,根据Java内存模型,现在newTable和table中的Entry都是主存中最新值:7.next=3,3.next=null。
此时切换到线程A上,在线程A挂起时内存中值如下:e=3,next=7,newTable[3]=null,代码执行过程如下:
newTable[3]=e ----> newTable[3]=3
e=next ----> e=7
此时结果如下:
继续循环:
e=7
next=e.next ----> next=3【从主存中取值】
e.next=newTable[3] ----> e.next=3【从主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3
结果如下:
再次进行循环:
e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7 即:3.next=7
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null
注意此次循环:e.next=7,而在上次循环中7.next=3,出现环形链表,并且此时e=null循环结束。
结果如下:
在后续操作中只要涉及轮询的数据结构,就会在这里发生死循环,造成悲剧。面试必问的:,推荐大家看下。
1.2 扩容造成数据丢失分析过程
遵照上述分析过程,初始时:
线程A和线程B进行put操作,同样线程A挂起:
此时线程A的运行结果如下:
此时线程B已获得CPU时间片,并完成resize操作:
同样注意由于线程B执行完成,newTable和table都为最新值:5.next=null。
此时切换到线程A,在线程A挂起时:e=7,next=5,newTable[3]=null。
执行newtable[i]=e,就将7放在了table[3]的位置,此时next=5。接着进行下一次循环:
e=5
next=e.next ----> next=null,从主存中取值
e.next=newTable[1] ----> e.next=5,从主存中取值
newTable[1]=e ----> newTable[1]=5
e=next ----> e=null
将5放置在table[1]位置,此时e=null循环结束,3元素丢失,并形成环形链表。并在后续操作时造成死循环。
2
jdk1.8中HashMap
在jdk1.8中对进行了优化,在发生hash碰撞,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程的情况下仍然不安全。
这里我们看jdk1.8中的put操作源码:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
这是jdk1.8中中put操作的主函数, 注意第6行代码,如果没有hash碰撞则会直接插入元素。
如果线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,所以这线程A、B都会进入第6行代码中。
假设一种情况,线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取时间片,此时线程A不用再进行hash判断了,问题出现:线程A会把线程B插入的数据给覆盖,发生线程不安全。
总结
首先是线程不安全的,其主要体现:
在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。
在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。
———END———
限 时 特 惠: 本站每日持续更新海量各大内部创业教程,一年会员只需98元,全站资源免费下载 点击查看详情
站 长 微 信: wxii2p22