JDK1.7 HashMap死循环形成的原因是什么？

╰半橙微兮° 2023-01-03 04:48 200阅读 0赞

这篇文章就只分析HashMap死循环形成的原因，死循环只在JDK1.7出现。

**原因**：死循环形成是在`扩容`转移元素的时候发生的

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

发生的具体时机在transfer函数中，默认情况下rehash为false

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

### 正常的transfer过程 ###

例子不考虑扩容阈值，假设放4个元素时开始扩容  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70]  
主要有2个有意思的地方

1.  原来在oldTable\[i\]位置的元素，会被放到newTable\[i\]或者newTable\[i+oldTable.length\]的位置
2.  链表在复制的时候会**反转**

### 并发下异常的transfer ###

假设线程1执行完`Entry<K,V> next = e.next`后被挂起，此时e指向key3，next指向key7

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; // 线程1执行完这一句被挂起
                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;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 1]  
线程2也来执行transfer函数，并执行完成，此时的状态为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 2]  
**触发时机**：此时线程1接着执行余下的代码，将key3放到线程1的table\[3\]处  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 3]  
接着将e指向key7，不为null，再次进入循环，将next指向key3如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 4]  
当跑完这次循环时key7被放入线程1的table中，e指向key3，next指向null![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 5]  
e不为null，还能再次执行循环，key3再次插入线程1中table\[3\]的头节点，此时e变为null,循环完毕。结构如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 6]  
环形链表形成，此时无论将线程1还是线程2的table设置为newTable，当调用get方法执行到这条链上时，死循环形成

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70]: /images/20221119/5fbc489c563248bb98ad25ef88c20a59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 1]: /images/20221119/1fd2e2d52d7c44c0801d5de75d7e1803.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 2]: /images/20221119/57b694c5082a4c508ae408a709aa4d18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 3]: /images/20221119/13d7bf2e1b4f4a989b882e017b645e44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 4]: /images/20221119/19a0e717b7e54282bc586d9a3dfb25da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 5]: /images/20221119/2abe1f8346104345a8c98246b6c30f6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70 6]: /images/20221119/7f5580930bf0491f92de4e65f6bb85af.png