【Java面试】HashMap死循环问题

布满荆棘的人生 2024-03-31 13:20 65阅读 0赞

## 问题 ##

最近几道面试题被问了是否了解并发情况下JDK7中HashMap发生死循环，导致CPU占用100%的问题。  
由于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题，这是一个普遍的问题。

如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发执行，在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，你会惊讶的发现，线程都Hang在hashMap的get()方法上，服务重启之后，问题消失，过段时间可能又复现了。  
这是为什么？

## 原因分析 ##

在了解来龙去脉之前，我们先看看JDK7中HashMap的数据结构。  
在内部，HashMap使用一个Entry数组保存key、value数据（JDK8之后是Node），当一对key、value被加入时，会通过一个hash算法得到数组的下标index，算法很简单，根据key的hash值，对数组的大小取模 hash & (length-1)，并把结果插入数组该位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。  
如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。  
当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash。

## JDK7中HashMap代码 ##

HashMap的put方法实现：  
1、判断key是否已经存在

public V put(K key, V value) {
        
    if (key == null)
    return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // 如果key已经存在，则替换value，并返回旧值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    modCount++;
    // key不存在，则插入新的元素
    addEntry(hash, key, value, i);
    return null;
    }

2、检查容量是否达到阈值threshold

void addEntry(int hash, K key, V value, int bucketIndex) {
        
    if ((size >= threshold) && (null != table[bucketIndex])) {
        
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
    }

3、扩容实现

void resize(int newCapacity) {
        
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ...
    Entry[] newTable = new Entry[newCapacity];
    ...
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

这里会新建一个更大的数组，并通过transfer方法，移动元素。

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

第一个for循环是遍历原来的table，第二个while循环用于遍历table中每个位置的链表。也就是如果这次的Entry节点下面有链表，就会执行while循环。  
由于JDK7的时候HashMap使用的是**头插法**，因此先来的数据会在链表尾部，后来的数据在链表头部。其实插入数据的时候是先让要插入节点的next指针指向原有的数据，然后再覆盖掉原有的数据。  
例如插入数据的顺序是1,2,3，那么插入完毕之后链表如下所示。  
![在这里插入图片描述][bf664775d05c4e2aa7c0edc8312ff49d.png]

## 单线程情况： ##

此时假设我们开始扩容，那么就会执行transfer函数。其中newTable就是扩容后的数组，其大小为原数组的两倍。  
我们现在开始外层for循环，现在我们遍历到了3这个Entry了。  
由于这个Entry不等于null，所以会执行while语句中的内容。  
首先我们的e一开始是3，那么e.next就是2  
之后开始进行rehash操作，然后得到hash值之后，我们根据这个hash值在扩容后的HashMap中获取新的插入位置的索引 i。  
并且让e（3）的next指针指向这个新数组的索引为i的位置，如下：  
![在这里插入图片描述][0dd9612b40f84530bacb00a3a3225b69.png]  
之后执行newTable\[i\]=e这个语句，那么根据头插法，变成如下：  
![在这里插入图片描述][cd921afc07044cc2a5044e7f322a543e.png]  
之后执行e=next，也就是让e指针指向2。  
![在这里插入图片描述][b0173b6e3a394ee0b2e872ff7453bc3d.png]  
然后继续执行while中的逻辑进行头插法操作，就会发现最后的结果是这样子的。  
![在这里插入图片描述][7544ab2944c7461b8356bc4b4158a35b.png]  
可以发现单线程的情况下执行头插法进行扩容是没有问题的。  
移动的逻辑也很清晰，遍历原来table中每个位置的链表，并对每个元素进行重新hash，在新的newTable找到归宿，并插入。（JDK8之后由于只需要两次扰动，因此性能更高，并且元素在newTable的索引要么为原本的索引位置，要么为原索引位置+此次扩容的大小）

## 多线程情况： ##

这里假设有两个线程进行扩容方法，那么就是有两个线程进入了resize方法，假设两个线程都执行到了transfer方法，并且两个线程都执行到了下面这一步，在这个时候，如果有一个线程阻塞住了。

if (rehash) {
        
    	e.hash = null == e.key ? 0 : hash(e.key);
    }

那么此时的table情况如下：  
![在这里插入图片描述][9802a12e24c94e789a52b97048d0d1a0.png]  
这两个e其实在线程之间是不互相影响的，他们在各自的线程的私有栈中。  
这里假设第一个线程他在运行，另一个线程阻塞，那么第一个线程就会先进行扩容。  
然后此时就和单线程扩容情况一样，扩容后如下：  
![在这里插入图片描述][7544ab2944c7461b8356bc4b4158a35b.png]  
此时线程2醒了，由于线程2的e指针和e.next指向的是3和2，那么由于线程1扩容之后，值没有改变，所以线程2醒来之后的情况如下：  
![在这里插入图片描述][81c89f605cb54ec08131fc05c664ee38.png]  
可以发现虽然他们指向的值没有变，但是顺序已经变了，e.next.next=e  
而本来应该是e.next=2，e=3这种情况的，所以他们的顺序已经相反了。  
然后我们再来一下线程2的扩容：  
我们刚才设定从if代码出开始阻塞，那么阻塞结束了继续进行，得到hash值之后获取在newTable中的索引位置。  
然后开始第一次插入：  
也就是e.next先指向扩容后数组的某个位置  
![在这里插入图片描述][7509b768a38b4300b8af52ef1359b085.png]  
![在这里插入图片描述][49ca2d53ca154e3bb7fc6db42d1849b7.png]  
![在这里插入图片描述][2b74300afc084c67a86d01debc95f4c0.png]  
到此第一次循环结束，可以发现好像没有问题，然后我们开始第二次循环：  
此时next为3，以为e此时为2，e.next由于一开始倒置的问题变为了3  
![在这里插入图片描述][fa2bbf9fe84e43808019c2a57d881f49.png]  
![在这里插入图片描述][52d3e6252b38471c908ff8d03b11d9a2.png]  
![在这里插入图片描述][24ecd5327aa44f798d401c52092191fa.png]  
之后我们第三次进入while循环  
此时的e.next就是NULL了，然后再让e.next指向newTable\[i\]，如下：  
![在这里插入图片描述][e809ed5122b44d7ba156c0c2aec8052c.png]  
此时可以发现已经生成了一个环形了，那么3的next是2 ， 2的next又是3，那么就是无论如何这个e和e.next都在2和3之间跳动了，那么就会导致卡死再这里。  
这就是再JDK7下多线程情况下HashMap的并发问题。  
他会在扩容的时候从一个链表变成一个环状结构。

[bf664775d05c4e2aa7c0edc8312ff49d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/cd4c088e4d384be692ffd00154d39289.png
[0dd9612b40f84530bacb00a3a3225b69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c1631ad39f484e5da3eb9286e88994c3.png
[cd921afc07044cc2a5044e7f322a543e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/093d8233349544c5b78cd12aafa1cadc.png
[b0173b6e3a394ee0b2e872ff7453bc3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/96a01a08b93e489691fb0ba67d3b23bd.png
[7544ab2944c7461b8356bc4b4158a35b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/94cbbcf32ceb433bac71010790b18859.png
[9802a12e24c94e789a52b97048d0d1a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/033a611f8227467ea875b3b18ab977b1.png
[81c89f605cb54ec08131fc05c664ee38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0ba5e3abeac2440c9dc09b9b7fb6c124.png
[7509b768a38b4300b8af52ef1359b085.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6e229c16b5f54f729e6af0d5a7d223fd.png
[49ca2d53ca154e3bb7fc6db42d1849b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c47a1beea38c41ac833277c1d969b7d6.png
[2b74300afc084c67a86d01debc95f4c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f6dcb94985ba4ef9b3172d842bddcf43.png
[fa2bbf9fe84e43808019c2a57d881f49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/34bfef89d72a437692ce22d9ef4f564c.png
[52d3e6252b38471c908ff8d03b11d9a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7a65d4a533fc4c56b83751f374f0f3e0.png
[24ecd5327aa44f798d401c52092191fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/561e0a0df06941149e26944f0b081a9a.png
[e809ed5122b44d7ba156c0c2aec8052c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3bfb1e9fec29487a816ccde06d0cb08a.png