面试官问:HashMap在并发情况下为什么造成死循环?一脸懵

2019/04/10 10:10
阅读数 20

这个问题是在面试时常问的几个问题,一般在问这个问题之前会问Hashmap和HashTable的区别?面试者一般会回答:hashtable是线程安全的,hashmap是线程不安全的。

那么面试官就会紧接着问道,为什么hashmap不是线程安全的,会造成什么问题么?于是面试者就回答:HashMap在并发情况下的put操作会造成死循环。

这时候就会被面试官问:HashMap在并发为什么造成死循环?

很多面试者这时候就会一脸懵。没有过相关经验和深入的理解源码是很难回答这个问题的。

下面我们就通过HahMap源码来验证下,多线程并发put操作为何会生成环形链表,产生死循环。

这是HashMap扩容的源码

/**
 * Transfers all entries from current table to newTable. 
 */
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];
            newTable[i] = e;
            e = next;
        } // while  

    }
}

开始之前先回顾一下HashMap的扩容机制: HashMap默认设定的装载因子为0.75(可改),HashMap的大小为length,已经装载的元素数量为num,当( num / length )> 装载因子时, 开始扩容

先创建一个散列表HashMap:Map<Integer> map = new HashMap<Integer>(2); ,装载因子默认0.75,当插入第二个元素时,会发生扩容 我们先在map中放入6、8两个元素。

<img src="https://upload-images.jianshu.io/upload_images/2710833-7d3073375b3cdc66.png" alt="插入后的状态" style="zoom: 33%;" />

这时有两个线程都执行put操作,那么在此刻两个线程都对HashMap进行扩容,这时候就注意在上文的源码里注释为(关键代码)这一行:Entry<K,V> next = e.next;

假如两个线程分别为A、B两个线程。A线程在执行到关键代码这一行线程就被挂起,那么此刻A线程中:e = 6; next = 8;

接着B线程开始进行扩容,假设新的散列表中,节点6 和 节点8 还是会产生散列冲突,那么线程B的扩容过程为:

  • 先申请一个空间为旧散列表两倍大的空间

    <img src="https://upload-images.jianshu.io/upload_images/2710833-091c030487692445.png" alt="申请两倍大小的空间" style="zoom:33%;" />

  • 将节点6 迁移至新散列表

    <img src="https://upload-images.jianshu.io/upload_images/2710833-fc1de798b8b2cbac.png" alt="节点6迁移至新散列表" style="zoom:33%;" />

  • 将节点8 迁移至新散列表

    <img src="https://upload-images.jianshu.io/upload_images/2710833-0f2c54f633bc98a2.png" alt="将节点8 迁移至新散列表" style="zoom:33%;" />

此时线程B的扩容已经完成,节点8 的后继节点为节点6 ,节点6的后继节点为null。

我们将新旧两个散列表做个对比:

<img src="https://upload-images.jianshu.io/upload_images/2710833-e7602e1bc90df913.png" alt="对比" style="zoom:33%;" />

回顾一下线程A的当前状态:e = 6; next = 8;,处于挂起状态。接着A线程取消挂起状态,接着执行(关键代码)之后的代码:将e = 6;节点迁移至新的散列表,并将next = 8的节点赋值给e。扩容并迁移节点6后的状态,如下图所示:

<img src="https://upload-images.jianshu.io/upload_images/2710833-6afb621e42838e56.png" alt="A线程扩容迁移节点6" style="zoom: 50%;" />

于是第二次执行while循环时,当前待处理节点:e = 8;

在执行(关键代码)这一行时,由于线程B在扩容时将节点8的后继节点变为节点6,所以next不是为null,而是next = 6;

<img src="https://upload-images.jianshu.io/upload_images/2710833-fb4ac06e60bc55fe.png" alt="dsa" style="zoom: 50%;" />

接着开始执行第三次while循环,由于节点6的后继节点为null,所以 next = null;,执行完第三次while循环的结果为:

<img src="https://upload-images.jianshu.io/upload_images/2710833-ebda06c0f55e4409.png" alt="321312" style="zoom:50%;" />

循环结束。

可以看到扩容后的散列表中链表成环,如果这时候执行get()方法查询,就会导致死循环。

总结

HashMap的方法不是线程安全的。HashMap在并发执行put操作时发生扩容,可能会导致节点丢失,产生环形链表等情况。

  • 节点丢失,会导致数据不准
  • 生成环形链表,会导致get()方法死循环。

知识拓展

在jdk1.7中,由于扩容时使用头插法,在并发时可能会形成环状列表,导致死循环,在jdk1.8中改为尾插法,可以避免这种问题,但是依然避免不了节点丢失的问题。

建议

HashMap的设计初衷就不是在并发情况下使用,如果有并发的场景,推荐使用ConcurrentHashMap

关注公众号:java之旅

原文出处:https://www.cnblogs.com/chinaxieshuai/p/12433179.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部