問題的癥狀

從前我們的Java代碼因?yàn)橐恍┰蚴褂昧薍ashMap這個(gè)東西，但是當(dāng)時(shí)的程序是單線程的，一切都沒有問題。后來，我們的程序性能有問題，所以需要變成多線程的，于是，變成多線程后到了線上，發(fā)現(xiàn)程序經(jīng)常占了100%的CPU，查看堆棧，你會發(fā)現(xiàn)程序都Hang在了HashMap.get()這個(gè)方法上了，重啟程序后問題消失。但是過段時(shí)間又會來。而且，這個(gè)問題在測試環(huán)境里可能很難重現(xiàn)。

Hash表數(shù)據(jù)結(jié)構(gòu)

HashMap通常會用一個(gè)指針數(shù)組(假設(shè)為table[])來做分散所有的key，當(dāng)一個(gè)key被加入時(shí)，會通過Hash算法通過key算出這個(gè)數(shù)組的下標(biāo)i，然后就把這個(gè)插到table[i]中，如果有兩個(gè)不同的key被算在了同一個(gè)i，那么就叫沖突，又叫碰撞，這樣會在table[i]上形成一個(gè)鏈表。

我們知道，如果table[]的尺寸很小，比如只有2個(gè)，如果要放進(jìn)10個(gè)keys的話，那么碰撞非常頻繁，于是一個(gè)O(1)的查找算法，就變成了鏈表遍歷，性能變成了O(n)，這是Hash表的缺陷。

所以，Hash表的尺寸和容量非常的重要。一般來說，Hash表這個(gè)容器當(dāng)有數(shù)據(jù)要插入時(shí)，都會檢查容量有沒有超過設(shè)定的thredhold，如果超過，需要增大Hash表的尺寸，但是這樣一來，整個(gè)Hash表里的元素都需要被重算一遍。這叫rehash，這個(gè)成本相當(dāng)?shù)拇蟆?/p>

HashMap的rehash源代碼

Put一個(gè)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不存在，需要增加一個(gè)結(jié)點(diǎn)
    addEntry(hash, key, value, i);
    return null;
}

檢查容量是否超標(biāo)

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);
    //查看當(dāng)前的size是否超過了我們設(shè)定的閾值threshold，如果超過，需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

新建一個(gè)更大尺寸的hash表，然后把數(shù)據(jù)從老的Hash表中遷移到新的Hash表中

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //創(chuàng)建一個(gè)新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //將Old Hash Table上的數(shù)據(jù)遷移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面這段代碼的意思是：
    //  從OldTable里摘一個(gè)元素出來，然后放到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);
        }
    }
}

以上就是關(guān)于“HashMap死循環(huán)：HashMap Infinite Loop”的介紹，如果您想了解更多相關(guān)知識，可以關(guān)注一下動(dòng)力節(jié)點(diǎn)的Java基礎(chǔ)教程，里面的課程內(nèi)容全面細(xì)致，通俗易懂，適合初學(xué)者學(xué)習(xí)，希望對大家能夠有所幫助。