模拟jdk1.7HashMap多线程下扩容死循环问题

谁借莪１个温暖的怀抱￠ 2022-12-25 11:52 113阅读 0赞

引发死循环的原因主要在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;
                }
            }
        }

transfer的作用就是把原来旧数组的内容转移到新数组newTable上，在转移的时候jdk1.7中使用了头插法来处理索引相同的元素。在单线程情况下，这样是安全的，但是当存在多个线程在同时扩容时候，由于头插法会将原来的链表顺序倒置，所以会出现产生循环链表的情况。  
在jdk1.7下对死循环问题进行模拟，代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class ThredDemo { 
        public static void main(String[] args) { 
            Mythread t1 = new Mythread();
    
            for (int i = 0; i < 100; i++) { 
                new Thread(t1).start();
            }
        }
    }
    
    class Mythread implements Runnable { 
        public Map<Integer, Integer> map = new HashMap<Integer, Integer>(2);
        public static int i = 0;
    
        @Override
        public void run() { 
            while (i < 100000) { 
                map.put(i, i);
                i++;
            }
        }
    
    }

调试模式运行后cpu占用持续百分之99  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20201201183655912.png]  
在transfer函数里打断点，程序暂停，从图中可以看到e为406->406，next也是406->406，找到406所对应的在newTable的元素，可以看到这个元素发生了自环，next指向的还是自己。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70 2]  
运行结果为什么是自己指向自己而不是大多数分析的AB两个元素循环指向，还有待研究

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70]: /images/20221120/57eae625f1474837aee57576e58534e1.png
[20201201183655912.png]: /images/20221120/dbb264b2bd414868bd3e6ad6f5cd2453.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70 1]: /images/20221120/59456ee5adc24fb981be62d55d08d917.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODM5MTUw_size_16_color_FFFFFF_t_70 2]: /images/20221120/9ac075056c12493b9a99dfd9a4f5d5e2.png