jdk1.7 hashmap的循環(huán)依賴問題是面試經(jīng)常被問到的問題家破，如何回答不好仓坞，可能會被扣分碍讯。今天我就帶大家一下梳理一下，這個問題是如何產(chǎn)生的扯躺，以及如何解決這個問題捉兴。
一、hashmap的數(shù)據(jù)結(jié)構(gòu)
先一起看看jdk1.7 hashmap的數(shù)據(jù)結(jié)構(gòu)
數(shù)組 + 鏈表
hashmap會給每個元素的key生成一個hash值录语，然后根據(jù)這個hash值計算一個在數(shù)組中的位置i倍啥。i不同的元素放在數(shù)組的不同位置，i相同的元素放在鏈表上澎埠，最新的數(shù)據(jù)放在鏈表的頭部虽缕。
往hashmap中保存元素會調(diào)用put方法，獲取元素會調(diào)用get方法蒲稳。接下來氮趋，我們重點看看put方法。
二江耀、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);
//計算在數(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) {
// 當數(shù)組的size >= 擴容閾值祥国，觸發(fā)擴容昵观，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);
}
// 創(chuàng)建一個新的鏈表節(jié)點舌稀，點進去可以了解到是將新節(jié)點添加到了鏈表的頭部
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;
}
// 創(chuàng)建2倍大小的新數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將舊數(shù)組的鏈表轉(zhuǎn)移到新數(shù)組啊犬，就是這個方法導致的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;
// 遍歷舊數(shù)組
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);
}
// 計算節(jié)點在新數(shù)組中的下標
int i = indexFor(e.hash, newCapacity);
// 將舊節(jié)點插入到新節(jié)點的頭部
e.next = newTable[i];
//這行才是真正把數(shù)據(jù)插入新數(shù)組中，前面那行代碼只是設置當前節(jié)點的next
//這兩行代碼決定了倒序插入
//比如：以前同一個位置上是:3睡腿，7语御，后面可能變成了：7领斥、3
newTable[i] = e;
//將下一個元素賦值給當前元素，以便遍歷下一個元素
e = next;
}
}
}
我來給大家分析一下沃暗，為什么這幾個代碼是頭插法，網(wǎng)上很多技術(shù)文章都沒有說清楚何恶。
三孽锥、頭插法
我們把目光聚焦到這幾行代碼：
//獲取下一個元素，記錄到一個臨時變量细层，以便后面使用
Entry<K,V> next = e.next;
// 計算節(jié)點在新數(shù)組中的下標
int i = indexFor(e.hash, newCapacity);
// 將舊節(jié)點插入到新節(jié)點的頭部
e.next = newTable[i];
//這行才是真正把數(shù)據(jù)插入新數(shù)組中惜辑，前面那行代碼只是設置當前節(jié)點的next
newTable[i] = e;
//將下一個元素賦值給當前元素，以便遍歷下一個元素
e = next;
假設剛開始hashMap有這些數(shù)據(jù)
調(diào)用put方法需要進行一次擴容疫赎，剛開始會創(chuàng)建一個空的數(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ù)組的元素為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 ，此時相同位置上已經(jīng)有key=3的值了胎撇，將該值賦值給當前元素的next
e.next = newTable[i];
//給新數(shù)組i位置 賦值 7
newTable[i] = e;
// e = 5
e = next;
上面會構(gòu)成一個新鏈表介粘，連接的順序正好反過來了。
由于第二次循環(huán)時晚树，節(jié)點key=7的元素插到相同位置上已有元素key=3的前面姻采，所以說是采用的頭插法。
四爵憎、死循環(huán)的產(chǎn)生
接下來重點看看死循環(huán)是如何產(chǎn)生的慨亲？
假設數(shù)據(jù)跟元素數(shù)據(jù)一致，有兩個線程：線程1 和 線程2宝鼓，同時執(zhí)行put方法刑棵，最后同時調(diào)用transfer方法。
線程1 先執(zhí)行愚铡，到 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 創(chuàng)建的數(shù)組會創(chuàng)建一個空數(shù)組
接下來茂附，線程2開始執(zhí)行正蛙，由于線程2運氣比較好，沒有被中斷過营曼，執(zhí)行完畢了乒验。
過一會兒，線程1被恢復了蒂阱，重新執(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ù)組的元素為null
e.next = newTable[i];
// 給新數(shù)組i位置 賦值 3
newTable[i] = e;
// e = 7
e = next;
這時候線程1的數(shù)組會變成這樣的
再執(zhí)行第二輪循環(huán)，此時的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鳄厌，此時相同位置上已經(jīng)有key=3的值了荞胡，將該值賦值給當前元素的next
e.next = newTable[i];
// 給新數(shù)組i位置 賦值 7
newTable[i] = e;
// e = 3
e = next;
這里特別要說明的是 此時e=7，而e.next為什么是3呢了嚎？
因為hashMap的數(shù)據(jù)是公共的泪漂，還記得線程2中的生成的數(shù)據(jù)嗎？
此時e=7歪泳，那么e.next肯定是3萝勤。
經(jīng)過上面第二輪循環(huán)之后，線程1得到的數(shù)據(jù)如下：
此時由于循環(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 = null
e = next;
由于e=null，此時會退出循環(huán)癣防，最終線程1的數(shù)據(jù)會是這種結(jié)構(gòu)：
key:3 和 key:7又恢復了剛開始的順序舵抹，但是他們的next會相互引用，構(gòu)成環(huán)形引用劣砍。
五惧蛹、如何避免死循環(huán)
為了解決這個問題，jdk1.8把擴容是復制元素到新數(shù)組由 頭插法 改成了 尾插法 刑枝。此外香嗓，引入了紅黑樹，提升遍歷節(jié)點的效率装畅。在這里我就不過多介紹了靠娱，
此外，HashMap是非線程安全的掠兄，要避免在多線程的環(huán)境中使用HashMap像云，而應該改成使用ConcurrentHashMap。
所以總結(jié)一下要避免發(fā)生死循環(huán)的問題的方法：改成ConcurrentHashMap
聯(lián)合http://www.reibang.com/p/1e9cf0ac07f4一起理解更清楚
