jdk1.7 HashMap中的致命错误：循环链表

拼搏现实的明天。 2023-07-24 05:42 25阅读 0赞

## jdk1.7 HashMap中的"致命错误"：循环链表 ##

### jdk1.7 HashMap结构图 ###

#### jdk1.7是数组+链表的结构 ####

![format_png][]

### jdk1.7版本中主要存在两个问题 ###

1.  头插法会造成循环链表的情况
2.  链表过长，会导致查询效率下降

### jdk1.8版本针对jdk1.8进行优化 ###

1.  使用尾插法，消除出现循环链表的情况
2.  链表过长后，转化为红黑树，提高查询效率

具体可以参考我的另一篇博客[你真的懂大厂面试题：HashMap吗？][HashMap]

### 循环链表的产生 ###

多线程同时`put`时，如果同时调用了`resize`操作，可能会导致循环链表产生，进而使得后面get的时候，会死循环。下面详细阐述循环链表如何形成的。

#### resize函数 ####

数组扩容函数,主要的功能就是创建扩容后的新数组，并且将调用`transfer`函数将旧数组中的元素迁移到新的数组

void resize(int newCapacity)
    { 
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        ......
        //创建一个新的Hash Table
        Entry[] newTable = new Entry[newCapacity];
        //将Old Hash Table上的数据迁移到New Hash Table上
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

#### transfer函数 ####

transfer逻辑其实也简单，遍历旧数组，将旧数组元素通过**头插法**的方式，迁移到新数组的对应位置问题出就出在**头插法**。

void transfer(Entry[] newTable)
    { 
        //src旧数组
        Entry[] src = table;
        int newCapacity = newTable.length;
     
        for (int j = 0; j < src.length; j++) { 
            Entry<K,V> e = src[j];
            if (e != null) { 
                src[j] = null;
                do { 
                    Entry<K,V> next = e.next; 
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);//由于是链表，所以有个循环过程
            }
        }
    }
    
    static int indexFor(int h, int length){ 
        return h&(length-1);
    }

#### 下面举个实际例子 ####

//下面详细解释需要用到这部分代码，所以先标号，将一下代码分为五个步骤
    do { 
    	1、Entry<K,V> next = e.next; 
    	2、int i = indexFor(e.hash, newCapacity);
    	3、e.next = newTab[i];
    	4、newTable[i] = e;
    	5、e= next;
    } while(e != null)

*  #### 开始 H a s h M a p HashMap HashMap容量设为2，加载阈值为 2 ∗ 0.75 = 1 2\*0.75=1 2∗0.75=1 ####
    
    ![format_png 1][]
 *  #### 线程 T 2 T\_2 T2和线程 T 1 T\_1 T1同时插入元素，由于阈值为1，所以都需要调用`resize`函数，进行扩容操作 ####
    
    ![format_png 2][]
 *  #### 线程 T 1 T\_1 T1先阻塞于代码`Entry<K,V> next = e.next;`，之后线程 T 2 T\_2 T2执行完扩容操作 ####
    
    ![format_png 3][]
 *  #### 之后线程 T 1 T\_1 T1被唤醒，继续执行，完成一次循环后 ####
    
    开始 e → 3 e\\rightarrow3 e→3,  n e x t → 7 next\\rightarrow7 next→7, 执行下面代码后， e → 7 e\\rightarrow 7 e→7,  n e x t → 3 next\\rightarrow3 next→3
    
        2、int i = indexFor(e.hash, newCapacity);
        3、e.next = newTab[i];
        4、newTable[i] = e;
        5、e= next;
        1、Entry<K,V> next = e.next;
    
    ![format_png 4][]
 *  #### 线程  T 1 T\_1 T1执行第二次循环后 ####
    
    开始 e → 7 e\\rightarrow 7 e→7,  n e x t → 3 next \\rightarrow 3 next→3, 执行以下代码后， $e\\rightarrow3 $,  n e x t → n u l l next \\rightarrow null next→null
    
        2、int i = indexFor(e.hash, newCapacity);
        3、e.next = newTab[i];
        4、newTable[i] = e;
        5、e= next;
        1、Entry<K,V> next = e.next;
    
    ![format_png 5][]
 *  #### 线程T1执行第三次循环后，形成死循环 ####
    
    开始 e → 3 e\\rightarrow 3 e→3,  n e x t → n u l l next \\rightarrow null next→null, 执行以下代码后，  e → n u l l e\\rightarrow null e→null
    
        2、int i = indexFor(e.hash, newCapacity);
        3、e.next = newTab[i];
        4、newTable[i] = e;
        5、e= next;
        1、Entry<K,V> next = e.next;
    
    ![format_png 6][]

#### 假如你执行get(11), 11%4=3, 陷入死循环 ####

### 参考文献 ###

[JDK1.7 HashMap 导致循环链表][JDK1.7 HashMap]

[format_png]: /images/20230528/79137c9686704169abb9ea5974322602.png
[HashMap]: https://blog.csdn.net/zycxnanwang/article/details/105411796
[format_png 1]: /images/20230528/3ae1b1dc23ea4f54891f96704a45f69d.png
[format_png 2]: /images/20230528/4c80ee48e9cb41b49652b86d121b8758.png
[format_png 3]: /images/20230528/b9b288b21c72443fa518e34b4b75083f.png
[format_png 4]: /images/20230528/9b6aa0e1a4094173991d160cea414ea7.png
[format_png 5]: /images/20230528/1b557b696e48493d8ddc68530bdd67b9.png
[format_png 6]: /images/20230528/aeea86bc5d2b49e8be22e6f851e11c31.png
[JDK1.7 HashMap]: https://www.cnblogs.com/chanshuyi/p/java_collection_hashmap_17_infinite_loop.html