JDK1.8之前，HashMap#get操作死回圈問題剖析
- 寫在前面
- 問題原因
- 1、頭插法：
- 2、在并發環境下使用非執行緒安全的類
- 具體成環的情況分析
- 問題答疑
- 歡迎關注我的公眾號：JAVA技術百科
寫在前面
1、HashMap本身是執行緒不安全的（不管哪個jdk版本），所以請不要在并發訪問的場景下直接使用HashMap，
2、如果在并發訪問的場景下，建議采用concurrentHashMap，
問題原因
1、頭插法：
我們知道，在jdk1.8之前，hashMap的put操作，或擴容操作，針對hash沖突時采用的是拉鏈法（將沖突的物件以鏈表的形式串聯起來），新加入的沖突元素將會插到原有鏈表的頭部，
基本結構如圖：
設計思想：區域性原理，當時設計HashMap的大叔采用頭插法而沒有采用尾插法有一點考慮是性能優化，認為最近put進去的元素，被get的概率相對較其他元素大，采用頭插法能夠更快得獲取到最近插入的元素，
但頭插法的設計有一個特點，就是擴容之后，鏈表上的元素順序會反過來，這也是死回圈的一個重要原因，
2、在并發環境下使用非執行緒安全的類
這個前面也說了，正確使用HashMap也就不會有這個問題了，
具體成環的情況分析
我們看一下HashMap的put操作：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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++;
// 關注元素插入程序
addEntry(hash, key, value, i);
return null;
}
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);
if (size++ >= threshold)
// 擴容
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// ...省略部分
Entry[] newTable = new Entry[newCapacity];
// 原有資料遷移
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
重點關注上面的transfer方法：
它會讀取原有hashmap中的元素，通過do…while的形式遷移到新的hashmap中：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
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);
}
}
}
我們以一個實體說明這個問題：
問題答疑
1、有同學對圖中的紅色字有所疑惑，認為執行緒B對鏈表的操作，執行緒A怎么會看到呢？不是有執行緒可見性問題嗎？
首先得理解執行緒可見性的原因是因為有cpu快取，在執行緒執行之前，讀取了運算元，在操作程序中運算元都在CPU快取中，在執行緒沒有將運算元寫入主存之前，執行緒中對運算元的修改則對于其他執行緒是不可見的，
而在hashMap擴容的程序中，執行緒操作的是堆中的物件，執行緒持有的是對物件的參考，參考就是一個地址，對參考的修改就是對堆中物件的修改，執行緒B的操作對于執行緒A的操作是透明的，所以執行緒A能看到執行緒B對鏈表的修改，
歡迎關注我的公眾號：JAVA技術百科
在里面我會分享一些我的學習記錄，互相學習，共同成長，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239625.html
標籤：其他
上一篇：SpringBoot使用攔截器
下一篇：Java學習筆記——多執行緒