Java基础-HashMap链表成环问题

野性酷女 2022-12-04 01:15 165阅读 0赞

## 1.JDK7 中 HashMap 成环原因 ##

#### 1.1 成环的时机 ####

HashMap 扩容时  
多线程环境下

#### 1.2 成环的位置 ####

void transfer(Entry[] newTable, boolean rehash) { 
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) { 
                //e为空时循环结束
                while(null != e) { 
                    Entry<K,V> next = e.next; // 记录oldhash表中e.next
                    if (rehash) { 
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity); // rehash计算出数组的位置(hash表中桶的位置)
                    // 成环的代码主要是在这三行代码
                    // 首先插入是从头开始插入的
                    e.next = newTable[i]; // e要插入链表的头部， 所以要先将e.next指向new hash表中的第一个元素
                    newTable[i] = e; // 将e放入到new hash表的头部
                    e = next; // 转移e到下一个节点， 继续循环下去
                }
            }
        }

## 2.具体分析 ##

*  e.next = newTable\[i\]  
    newTable ：表示新的数组  
    newTable\[i\] ：表示新数组下标为 i 的值；第一次循环的时候为 null  
    e ：表示原来链表位置的头一个元素  
    e.next：表示原来链表位置的头一个元素的下一个元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]

*  newTable\[i\] = e  
    e：即是a  
    即，把a的值赋值给扩容后的新数组的首位  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 1]
 *  e = next  
    Entry<K,V> next = e.next  
    e.next 是在while循坏体的顶层，即， e.next == a.next == b  
    即，next的值就是 b 的值  
    即，此句代码就是把 b 赋值给 e，接着下一轮循环

#### 当有多条线程并发时： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 2]  
问题原因：  
1.头插法，导致插入的顺序和原来链表的顺序相反的  
2.table 是共享的，table 里面的元素也是共享的，while 循环都直接修改 table 里面的元素的 next 指向，导致指向混乱

## 2.jdk8解决方案 ##

**采用高低位拆分转移方式，避免了链表环的产生**

扩容前：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70]

扩容：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0f1738a334f947949ea42f0a8d9f778a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/18387c184cfb47869aa70f15e20fd20b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/1816a230ea5e44d4982fbf12ab083b70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70]: /images/20221123/eb367f6134fd4f39a44f8cdb0bf99d84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70 1]: /images/20221123/280b99c47f3d4120b23f715a5dabc426.png