jdk1.7 hashmap的循環依賴問題是面試經常被問到的問題，如何回答不好，可能會被扣分。今天我就帶大家一下梳理一下，這個問題是如何産生的，以及如何解決這個問題。
一、hashmap的資料結構
先一起看看jdk1.7 hashmap的資料結構
數組 + 連結清單
hashmap會給每個元素的key生成一個hash值，然後根據這個hash值計算一個在數組中的位置i。i不同的元素放在數組的不同位置，i相同的元素放在連結清單上，最新的資料放在連結清單的頭部。
往hashmap中儲存元素會調用put方法，擷取元素會調用get方法。接下來，我們重點看看put方法。
二、put方法
重點看看put方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//根據key擷取hash
int hash = hash(key);
//計算在數組中的下表
int i = indexFor(hash, table.length);
//變量集合查詢相同key的資料，如果已經存在則更新資料
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;
} 複制
再看看addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當數組的size >= 擴容門檻值，觸發擴容，size大小會在createEnty和removeEntry的時候改變
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴容到2倍大小，後邊會跟進這個方法
resize(2 * table.length);
// 擴容後重新計算hash和index
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 建立一個新的連結清單節點，點進去可以了解到是将新節點添加到了連結清單的頭部
createEntry(hash, key, value, bucketIndex);
} 複制
看看resize是如何擴容的
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 建立2倍大小的新數組
Entry[] newTable = new Entry[newCapacity];
// 将舊數組的連結清單轉移到新數組，就是這個方法導緻的hashMap不安全，等下我們進去看一眼
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 重新計算擴容門檻值(容量*加載因子)
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
} 複制
出問題的就是這個transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 周遊舊數組
for (Entry<K,V> e : table) {
// 周遊連結清單
while(null != e) {
//擷取下一個元素，記錄到一個臨時變量，以便後面使用
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 計算節點在新數組中的下标
int i = indexFor(e.hash, newCapacity);
// 将舊節點插入到新節點的頭部
e.next = newTable[i];
//這行才是真正把資料插入新數組中，前面那行代碼隻是設定目前節點的next
//這兩行代碼決定了倒序插入
//比如：以前同一個位置上是:3，7，後面可能變成了：7、3
newTable[i] = e;
//将下一個元素指派給目前元素，以便周遊下一個元素
e = next;
}
}
} 複制
我來給大家分析一下，為什麼這幾個代碼是頭插法，網上很多技術文章都沒有說清楚。
三、頭插法
我們把目光聚焦到這幾行代碼：
//擷取下一個元素，記錄到一個臨時變量，以便後面使用
Entry<K,V> next = e.next;
// 計算節點在新數組中的下标
int i = indexFor(e.hash, newCapacity);
// 将舊節點插入到新節點的頭部
e.next = newTable[i];
//這行才是真正把資料插入新數組中，前面那行代碼隻是設定目前節點的next
newTable[i] = e;
//将下一個元素指派給目前元素，以便周遊下一個元素
e = next; 複制
假設剛開始hashMap有這些資料
調用put方法需要進行一次擴容，剛開始會建立一個空的數組，大小是以前的2倍，如圖所示：
開始第一輪循環：
//next= 7 e = 3 e.next = 7
Entry<K,V> next = e.next;
// i=3
int i = indexFor(e.hash, newCapacity);
//e.next = null ，剛初始化時新數組的元素為null
e.next = newTable[i];
//給新數組i位置 指派 3
newTable[i] = e;
// e = 7
e = next; 複制
執行完之後，第一輪循環之後資料變成這樣的
再接着開始第二輪循環：
//next= 5 e = 7 e.next = 5
Entry<K,V> next = e.next;
// i=3
int i = indexFor(e.hash, newCapacity);
//e.next = 3 ，此時相同位置上已經有key=3的值了，将該值指派給目前元素的next
e.next = newTable[i];
//給新數組i位置 指派 7
newTable[i] = e;
// e = 5
e = next; 複制
上面會構成一個新連結清單，連接配接的順序正好反過來了。
由于第二次循環時，節點key=7的元素插到相同位置上已有元素key=3的前面，是以說是采用的頭插法。
四、死循環的産生
接下來重點看看死循環是如何産生的？
假設資料跟元素資料一緻，有兩個線程：線程1 和 線程2，同時執行put方法，最後同時調用transfer方法。
線程1 先執行，到 Entry<K,V> 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; 複制
此時線程1 建立的數組會建立一個空數組
接下來，線程2開始執行，由于線程2運氣比較好，沒有被中斷過，執行完畢了。
過一會兒，線程1被恢複了，重新執行代碼。
//next= 7 e = 3 e.next = 7
Entry<K,V> next = e.next;
// i = 3
int i = indexFor(e.hash, newCapacity);
// e.next = null，剛初始化時新數組的元素為null
e.next = newTable[i];
// 給新數組i位置 指派 3
newTable[i] = e;
// e = 7
e = next; 複制
這時候線程1的數組會變成這樣的
再執行第二輪循環，此時的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，此時相同位置上已經有key=3的值了，将該值指派給目前元素的next
e.next = newTable[i];
// 給新數組i位置 指派 7
newTable[i] = e;
// e = 3
e = next; 複制
這裡特别要說明的是 此時e=7，而e.next為什麼是3呢？
因為hashMap的資料是公共的，還記得線程2中的生成的資料嗎？
此時e=7，那麼e.next肯定是3。
經過上面第二輪循環之後，線程1得到的資料如下：
此時由于循環判斷還沒有退出，判斷條件是： while(null != e)，是以要開始第三輪循環：
//next= null e = 3 e.next = null
Entry<K,V> next = e.next;
// i = 3
int i = indexFor(e.hash, newCapacity);
// e.next = 7，關鍵的一步，由于第二次循環是 key:7 .next = key:3，現在key:3.next = key:7
e.next = newTable[i];
// 給新數組i位置 指派 3
newTable[i] = e;
// e = null
e = next; 複制
由于e=null，此時會退出循環，最終線程1的資料會是這種結構：
key:3 和 key:7又恢複了剛開始的順序，但是他們的next會互相引用，構成環形引用。
注意，此時調用hashmap的get方法擷取資料時，如果隻是擷取循環鍊上key:3 和 key:7的資料，是不會有問題的，因為可以找到。就怕擷取循環鍊上沒有的資料，比如：key:11，key:15等，會進入無限循環中導緻CPU使用率飙升。
五、如何避免死循環
為了解決這個問題，jdk1.8把擴容是複制元素到新數組由 頭插法 改成了 尾插法 。此外，引入了紅黑樹，提升周遊節點的效率。在這裡我就不過多介紹了，如果有興趣的朋友，可以關注我的公衆号，後面會給大家詳細分析jdk1.8的實作，以及 jdk1.7、jdk1.8 hashmap的差別。
此外，HashMap是非線程安全的，要避免在多線程的環境中使用HashMap，而應該改成使用ConcurrentHashMap。
是以總結一下要避免發生死循環的問題的方法：
- 更新jdk到1.8以上
- 改成ConcurrentHashMap
如果這篇文檔對您有所幫助的話，麻煩關注一下我的公衆賬号：蘇三說技術，或者幫忙點贊或轉發，堅持原創不易，您的支援是我堅持最大的動力。後面我會分享更多更實用的幹貨，謝謝大家的支援。