HashMap死循环问题

刺骨的言语ヽ痛彻心扉 2022-06-01 12:20 175阅读 0赞

# 0 说明 #

HashMap通常会用一个指针数组（假设为table\[\]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个<key, value>插到table\[i\]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table\[i\]上形成一个链表。

# 1 java中HashMap源码 #

（jdk8以前的）  
（0）先看流程图：  
![这里写图片描述][SouthEast]  
（1）Put一个Key,Value对到Hash表中：

public V put(K key, V value)
    {
        ......
        //算Hash值
        int hash = hash(key.hashCode());
        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）检查容量是否超标的函数：

void addEntry(int hash, K key, V value, int bucketIndex)
    {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
        if (size++ >= threshold)
            resize(2 * table.length);
    }

（3）新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

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

（4）迁移的源代码，注意高亮处：

void transfer(Entry[] newTable)
    {
        Entry[] src = table;
        int newCapacity = newTable.length;
        //下面这段代码的意思是：
        // 从OldTable里摘一个元素出来，然后放到NewTable中
        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);
            }
        }
    }

# 2 单线程正常执行的HashMap #

*  假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
 *  最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table\[1\]这里了。
 *  接下来的三个步骤是Hash表 resize成4，然后所有的<key,value > 重新rehash的过程  
    过程如下图：

![这里写图片描述][SouthEast 1]

#  3 并发下的Rehash #

（1） 线程1执行到如图位置挂起：

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

（2） 线程二执行完毕，此时线程一和线程二的状态如下图：  
![这里写图片描述][SouthEast 2]

【注意】，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

（3）线程一被调度回来执行  
\- 先是执行 newTalbe\[i\] = e;  
\- 然后是e = next，导致了e指向了key(7)，  
\- 而下一次循环的next = e.next导致了next指向了key(3)  
![这里写图片描述][SouthEast 3]

（4）线程一把key(7)摘下来，放到newTable\[i\]的第一个，然后把e和next往下移。  
![这里写图片描述][SouthEast 4]

（5）环形链接出现。  
e.next = newTable\[i\] 导致 key(3).next 指向了 key(7)  
【注意】：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。  
![这里写图片描述][SouthEast 5]

详细介绍请看：[https://coolshell.cn/articles/9606.html][https_coolshell.cn_articles_9606.html]

[SouthEast]: /images/20220601/bd363a03819549bf9591bf33ddb7bc88.png
[SouthEast 1]: /images/20220601/296bc71c68c34c6199af332799ed3270.png
[SouthEast 2]: /images/20220601/18ac98f577174885ae520b666d66d902.png
[SouthEast 3]: /images/20220601/9224d61db3484221888146f1fc67abe8.png
[SouthEast 4]: /images/20220601/ad6f18ebd0f34d009ae67f722309f188.png
[SouthEast 5]: /images/20220601/2e990c3eb3a844a4acc6e86c87cbca16.png
[https_coolshell.cn_articles_9606.html]: https://coolshell.cn/articles/9606.html