jdk1.7 hashmap的循環(huán)依賴問題是面試經(jīng)常被問到的問題，如何回答不好，可能會(huì)被扣分。今天我就帶大家一下梳理一下，這個(gè)問題是如何產(chǎn)生的，以及如何解決這個(gè)問題。

一、hashmap的數(shù)據(jù)結(jié)構(gòu)

先一起看看jdk1.7 hashmap的數(shù)據(jù)結(jié)構(gòu)

數(shù)組 + 鏈表

hashmap會(huì)給每個(gè)元素的key生成一個(gè)hash值，然后根據(jù)這個(gè)hash值計(jì)算一個(gè)在數(shù)組中的位置i。i不同的元素放在數(shù)組的不同位置，i相同的元素放在鏈表上，最新的數(shù)據(jù)放在鏈表的頭部。

往hashmap中保存元素會(huì)調(diào)用put方法，獲取元素會(huì)調(diào)用get方法。接下來，我們重點(diǎn)看看put方法。

二、put方法

重點(diǎn)看看put方法

public V put(K key, V value) { 
    if (table == EMPTY_TABLE) { 
        inflateTable(threshold);    }    if (key == null) 
        return putForNullKey(value); 
    //根據(jù)key獲取hash      
    int hash = hash(key);    //計(jì)算在數(shù)組中的下表 
    int i = indexFor(hash, table.length);    //變量集合查詢相同key的數(shù)據(jù)，如果已經(jīng)存在則更新數(shù)據(jù) 
    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);            //返回已有數(shù)據(jù) 
            return oldValue; 
        }    }    modCount++;    //如果不存在相同key的元素，則添加新元素 
    addEntry(hash, key, value, i);    return null; 
} 

再看看addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) { 
      // 當(dāng)數(shù)組的size >= 擴(kuò)容閾值，觸發(fā)擴(kuò)容，size大小會(huì)在createEnty和removeEntry的時(shí)候改變      if ((size >= threshold) && (null != table[bucketIndex])) { 
          // 擴(kuò)容到2倍大小，后邊會(huì)跟進(jìn)這個(gè)方法          resize(2 * table.length);          // 擴(kuò)容后重新計(jì)算hash和index 
          hash = (null != key) ? hash(key) : 0; 
          bucketIndex = indexFor(hash, table.length); 
      }      // 創(chuàng)建一個(gè)新的鏈表節(jié)點(diǎn)，點(diǎn)進(jìn)去可以了解到是將新節(jié)點(diǎn)添加到了鏈表的頭部      createEntry(hash, key, value, bucketIndex); 
  } 

看看resize是如何擴(kuò)容的

void resize(int newCapacity) { 
        Entry[] oldTable = table;        int oldCapacity = oldTable.length; 
        if (oldCapacity == MAXIMUM_CAPACITY) { 
            threshold = Integer.MAX_VALUE;            return; 
        }        // 創(chuàng)建2倍大小的新數(shù)組 
        Entry[] newTable = new Entry[newCapacity]; 
        // 將舊數(shù)組的鏈表轉(zhuǎn)移到新數(shù)組，就是這個(gè)方法導(dǎo)致的hashMap不安全，等下我們進(jìn)去看一眼 
        transfer(newTable, initHashSeedAsNeeded(newCapacity)); 
        table = newTable; 
        // 重新計(jì)算擴(kuò)容閾值(容量*加載因子) 
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 
} 

出問題的就是這個(gè)transfer方法

void transfer(Entry[] newTable, boolean rehash) { 
    int newCapacity = newTable.length;    // 遍歷舊數(shù)組 
    for (Entry<K,V> e : table) { 
        // 遍歷鏈表 
        while(null != e) { 
             //獲取下一個(gè)元素，記錄到一個(gè)臨時(shí)變量，以便后面使用 
            Entry<K,V> next = e.next; 
            if (rehash) { 
                e.hash = null == e.key ? 0 : hash(e.key); 
            }            // 計(jì)算節(jié)點(diǎn)在新數(shù)組中的下標(biāo) 
            int i = indexFor(e.hash, newCapacity); 
            // 將舊節(jié)點(diǎn)插入到新節(jié)點(diǎn)的頭部 
            e.next = newTable[i]; 
            //這行才是真正把數(shù)據(jù)插入新數(shù)組中，前面那行代碼只是設(shè)置當(dāng)前節(jié)點(diǎn)的next 
            //這兩行代碼決定了倒序插入 
            //比如：以前同一個(gè)位置上是:3，7，后面可能變成了：7、3 
            newTable[i] = e; 
            //將下一個(gè)元素賦值給當(dāng)前元素，以便遍歷下一個(gè)元素 
            e = next; 
        } 
    } 
} 

我來給大家分析一下，為什么這幾個(gè)代碼是頭插法，網(wǎng)上很多技術(shù)文章都沒有說清楚。

三、頭插法

我們把目光聚焦到這幾行代碼：

//獲取下一個(gè)元素，記錄到一個(gè)臨時(shí)變量，以便后面使用 
  Entry<K,V> next = e.next; 
  // 計(jì)算節(jié)點(diǎn)在新數(shù)組中的下標(biāo)  int i = indexFor(e.hash, newCapacity);  // 將舊節(jié)點(diǎn)插入到新節(jié)點(diǎn)的頭部  e.next = newTable[i]; 
  //這行才是真正把數(shù)據(jù)插入新數(shù)組中，前面那行代碼只是設(shè)置當(dāng)前節(jié)點(diǎn)的next 
  newTable[i] = e;  //將下一個(gè)元素賦值給當(dāng)前元素，以便遍歷下一個(gè)元素  e = next; 

假設(shè)剛開始hashMap有這些數(shù)據(jù)

調(diào)用put方法需要進(jìn)行一次擴(kuò)容，剛開始會(huì)創(chuàng)建一個(gè)空的數(shù)組，大小是以前的2倍，如圖所示：

開始第一輪循環(huán)：

//next= 7   e = 3  e.next = 7 
Entry<K,V> next = e.next; 
// i=3 
int i = indexFor(e.hash, newCapacity);//e.next = null ，剛初始化時(shí)新數(shù)組的元素為null 
e.next = newTable[i]; 
//給新數(shù)組i位置 賦值 3 
newTable[i] = e;// e = 7 
e = next; 

執(zhí)行完之后，第一輪循環(huán)之后數(shù)據(jù)變成這樣的

再接著開始第二輪循環(huán)：

//next= 5   e = 7  e.next = 5 
Entry<K,V> next = e.next; 
// i=3 
int i = indexFor(e.hash, newCapacity);//e.next = 3 ，此時(shí)相同位置上已經(jīng)有key=3的值了，將該值賦值給當(dāng)前元素的next 
e.next = newTable[i]; 
//給新數(shù)組i位置 賦值 7 
newTable[i] = e;// e = 5 
e = next; 

上面會(huì)構(gòu)成一個(gè)新鏈表，連接的順序正好反過來了。

由于第二次循環(huán)時(shí)，節(jié)點(diǎn)key=7的元素插到相同位置上已有元素key=3的前面，所以說是采用的頭插法。

四、死循環(huán)的產(chǎn)生

接下來重點(diǎn)看看死循環(huán)是如何產(chǎn)生的?

假設(shè)數(shù)據(jù)跟元素?cái)?shù)據(jù)一致，有兩個(gè)線程：線程1 和 線程2，同時(shí)執(zhí)行put方法，最后同時(shí)調(diào)用transfer方法。

線程1 先執(zhí)行，到 Entry next = e.next; 這一行，被掛起了。

//next= 7   e = 3  e.next = 7 
Entry<K,V> next = e.next; 
int i = indexFor(e.hash, newCapacity);e.next = newTable[i]; 
newTable[i] = e;e = next; 

此時(shí)線程1 創(chuàng)建的數(shù)組會(huì)創(chuàng)建一個(gè)空數(shù)組

接下來，線程2開始執(zhí)行，由于線程2運(yùn)氣比較好，沒有被中斷過，執(zhí)行完畢了。

過一會(huì)兒，線程1被恢復(fù)了，重新執(zhí)行代碼。

//next= 7   e = 3  e.next = 7 
Entry<K,V> next = e.next; 
// i = 3 
int i = indexFor(e.hash, newCapacity);// e.next = null，剛初始化時(shí)新數(shù)組的元素為null 
e.next = newTable[i]; 
// 給新數(shù)組i位置 賦值 3 
newTable[i] = e;// e = 7 
e = next; 

這時(shí)候線程1的數(shù)組會(huì)變成這樣的

再執(zhí)行第二輪循環(huán)，此時(shí)的e=7

//next= 3   e = 7  e.next = 3 
Entry<K,V> next = e.next; 
// i = 3 
int i = indexFor(e.hash, newCapacity);// e.next = 3，此時(shí)相同位置上已經(jīng)有key=3的值了，將該值賦值給當(dāng)前元素的next 
e.next = newTable[i]; 
// 給新數(shù)組i位置 賦值 7 
newTable[i] = e;// e = 3 
e = next; 

這里特別要說明的是 此時(shí)e=7，而e.next為什么是3呢?

因?yàn)閔ashMap的數(shù)據(jù)是公共的，還記得線程2中的生成的數(shù)據(jù)嗎?

此時(shí)e=7，那么e.next肯定是3。

經(jīng)過上面第二輪循環(huán)之后，線程1得到的數(shù)據(jù)如下：

此時(shí)由于循環(huán)判斷還沒有退出，判斷條件是： while(null != e)，所以要開始第三輪循環(huán)：

//next= null   e = 3  e.next = null 
Entry<K,V> next = e.next; 
// i = 3 
int i = indexFor(e.hash, newCapacity);// e.next = 7，關(guān)鍵的一步，由于第二次循環(huán)是 key:7 .next = key:3，現(xiàn)在key:3.next = key:7 
e.next = newTable[i]; 
// 給新數(shù)組i位置 賦值 3 
newTable[i] = e;// e = nulle = next; 

由于e=null，此時(shí)會(huì)退出循環(huán)，最終線程1的數(shù)據(jù)會(huì)是這種結(jié)構(gòu)：

key:3 和 key:7又恢復(fù)了剛開始的順序，但是他們的next會(huì)相互引用，構(gòu)成環(huán)形引用。

注意，此時(shí)調(diào)用hashmap的get方法獲取數(shù)據(jù)時(shí)，如果只是獲取循環(huán)鏈上key:3 和 key:7的數(shù)據(jù)，是不會(huì)有問題的，因?yàn)榭梢哉业健＞团芦@取循環(huán)鏈上沒有的數(shù)據(jù)，比如：key:11，key:15等，會(huì)進(jìn)入無限循環(huán)中導(dǎo)致CPU使用率飆升。

五、如何避免死循環(huán)

為了解決這個(gè)問題，jdk1.8把擴(kuò)容是復(fù)制元素到新數(shù)組由 頭插法 改成了 尾插法 。此外，引入了紅黑樹，提升遍歷節(jié)點(diǎn)的效率。在這里我就不過多介紹了，如果有興趣的朋友，可以關(guān)注我的公眾號，后面會(huì)給大家詳細(xì)分析jdk1.8的實(shí)現(xiàn)，以及 jdk1.7、jdk1.8 hashmap的區(qū)別。

此外，HashMap是非線程安全的，要避免在多線程的環(huán)境中使用HashMap，而應(yīng)該改成使用ConcurrentHashMap。

所以總結(jié)一下要避免發(fā)生死循環(huán)的問題的方法：

• 改成ConcurrentHashMap

PS. 即使JDK升級到1.8任然有死循環(huán)的問題。