HashMap死循环问题

我会带着你远行 2022-05-26 01:00 253阅读 0赞

大家都知道，相比于HashTable，HashMap是一个非线程安全的实现类。

为什么说HashMap是非线程安全的呢？因为在高并发情况下，HashMap在一些操作上会存在问题，如死循环问题，导致CPU使用率较高。

下面来看下怎么复现这个问题。如下代码所示，我们创建10个线程，这10个线程并发向一个HashMap种添加元素。

package com.majing.java.concurrent;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.concurrent.atomic.AtomicInteger;
    
    public class HashMapConcurrentProblem extends Thread{
    	
    	private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    	private static AtomicInteger at = new AtomicInteger(0);
    	
    
    	@Override
    	public void run() {
    		while(at.get()<1000000){
    			map.put(at.get(), at.get());
    			at.incrementAndGet();
    		}
    	}
    	
    	public static void main(String[] args) {
    		for(int i=0;i<10;i++){
    			Thread thread = new HashMapConcurrentProblem();
    			thread.start();
    		}
    	}
    	
    }

我们运行main方法后，发现代码一直卡死并没有退出。

![70][]

接下来我们jps和jsstack命令看下这个进程的状态。

![70 1][]

从上面看到，在HashMap的resize（扩容）过程中出现了问题。那么为什么在扩容时会出现问题呢？

**正常场景下的扩容**

我们先来看下单线程情况下，正常的rehash过程

1、假设我们的hash算法是简单的key mod一下表的大小（即数组的长度）。

2、最上面是old hash表，其中HASH表的size=2，所以key=3,5,7在mod 2 以后都冲突在table\[1\]这个位置上了。

3、接下来HASH表扩容，resize=4，然后所有的<key,value>重新进行散列分布，过程如下：

![70 2][]

在单线程场景下，扩容并不会出现什么问题。接下来看下并发情况下的扩容又会出现什么情况。

**并发场景下的扩容**

我们先把扩容相关的源码贴出来，结合着源码和图进行说明。

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);
        }

在resize()方法中，在创建了新的数组之后调用transfer方法来完成元素的迁移操作，具体迁移逻辑如下：

/**
         * 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;
                }
            }
        }

下面我们就来看下为什么上面的代码在并发情况下出现问题。假设有两个线程A和B，首先线程B完成了元素的迁移，效果如下：

![70 3][]

这里采用的hash算法就是按照简单的key mod newsize，这里我们看到key为3、5、7的元素都已经重新排序好了。需要注意的是，由于代码逻辑的原因，虽然key为3和7的元素还是落在同一个槽中，但是元素的顺序已经发生了改变。原来key=3的元素排在key=7元素的前面，在重新排序后顺序发生了转换。

目前一些安好，但是这时候如果线程A并发的执行上述transfer的代码，那么问题就来了，如下图所示

![70 4][]

在线程A执行transfer()方法的时候，在处理槽为3的列表元素时，首先处理的是key=7的元素，

newTable[i] = e;
    e = next;

上面线程A将e引用的节点赋值给扩容后新数组的第i个操作（也就是这里的槽位3）,紧接着e=next，将e执行了key=7的元素，在下一次while循环时，通过while循环中的

Entry<K,V> next = e.next;

将next指向了key=3的元素。紧接着，线程A继续工作，将key=7的元素赋值给新数组槽位3的首个元素，并且e和next引用往后移动一位，如下所示：

![70 5][]

这时候由于e还不为null，导致while循环继续执行，在while循环中，通过e.next = newTable\[i\];将key=7的元素作为了key=3元素的后继节点，之后newTable\[i\] = e;将新数组中槽位3的引用指向了key=3的元素，而最后e=next将e变成了null，从而退出了循环。此时槽位为3的位置中便出现了一个唤醒链表，HashMap中的存储结构变成了如下情况：

![70 6][]

这种情况下，如果线程调用获取Key=11的元素就会出现在换型链表中一直死循环的问题，因为一直找不到Key=11的元素，而又发现一直有后继节点，所以永远也跳不出循环，对于单核CPU而言，直接消耗100%的CPU，对于双核或者多核CPU，可能消耗的CPU占比要同比下降。

感谢大家的阅读，如果有对Java编程、中间件、数据库、及各种开源框架感兴趣，欢迎关注我的博客和头条号（源码帝国），博客和头条号后期将定期提供一些相关技术文章供大家一起讨论学习，谢谢。

如果觉得文章对您有帮助，欢迎给我打赏，一毛不嫌少，一百不嫌多，^\_^谢谢。

![20180312232547620][]

[70]: /images/20220526/94be7ab6867f4c6590643b3f2029bc56.png
[70 1]: /images/20220526/ee17892c4fc941da99b83e3a82fd33e2.png
[70 2]: /images/20220526/c80fac113a4d461498059995a2abdceb.png
[70 3]: /images/20220526/85fe603accb0431b9403cab0863b53e7.png
[70 4]: /images/20220526/380f80a43d1f4286b9bc740a216b67e9.png
[70 5]: /images/20220526/7fbe1176ae7445588fa424b1d2205d82.png
[70 6]: /images/20220526/88a5b0b8d65b4c118e3ad9fa7d784d16.png
[20180312232547620]: /images/20220526/7c00ed26d5fc4b4ab34ba7c3c7acf54c.png