多線程下HashMap是怎么死循環的？
這是一個老問題了，現在都Java21了，又翻出來Java7的問題，算是對歷史的總結把。
背過面試八股文的都知道，HashMap是非線程安全的，多線程下要用ConcurrentHashMap之類的。但是實際工作中，還是會碰到在多線程中使用HashMap?？赡苁菍懙臅r候迷糊了，也可能是代碼升級時沒有注意，比如原本是單線程的，后來性能不行改成多線程了。多線程下使用HashMap，偶爾會出現服務hang死的情況，重啟就好，測試環境還復現不了，純偶發，即Race Condition（競態條件）。
競態條件（Race Condition）是指在多線程或者多進程的程序中，由于多個線程或進程之間執行順序的不確定性，導致程序出現意料之外的結果或者行為。這種情況通常發生在多個線程或進程同時訪問共享資源時，其中一個線程或進程修改了共享資源的狀態，但其他線程或進程并沒有意識到這個修改，導致它們基于過期的狀態做出了錯誤的決策。競爭條件是一種常見的并發編程錯誤，需要在程序設計和實現時特別注意。
競態條件可能會導致程序崩潰、數據損壞、死鎖等問題。為了避免競爭條件，可以使用同步機制（如鎖、信號量等）來保證只有一個進程或線程可以訪問共享資源。
那我們來分析下，HashMap是怎么形成競態條件的。
先梳理一下源碼
put方法是入口：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
// 計算hash值
int hash = hash(key);
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不存在，增加一個節點
addEntry(hash, key, value, i);
return null;
}檢查容量是否超過閾值，超過了就擴容：
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判斷當前的size是否超過閾值，如果超過了，重新resize，也就是擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// size未超過閾值或者擴容完成后，增加節點
createEntry(hash, key, value, bucketIndex);
}將新增元素插入鏈表中：
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}擴容重建新的hash表，并將老表中的數據遷移到新表中：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 創建新的hash表
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
// 將老表中的數據遷移到新表中
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}老表數據遷移到新表，就是循環遍歷舊數據，然后插入的新表中：
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];
newTable[i] = e;
e = next;
}
}
}上面的這個代碼沒有什么問題，有問題也不會堅持這么多版本了。
那問題出在哪呢？出在了多線程上，接下來我們畫圖看看。
看圖說話
本節中的例子和圖片思路來源于酷殼。
假設我們的hash算法就是key mode表格大小，hash表size是2，當前元素key是3、5、7，mod 2時hash值都是1。執行resize成4時，所有元素遷移到新表數據，過程如下（下圖來源于酷殼）：
示例
上面的過程是正常運行的結果，如果在遷移時有兩個現成同時操作（能過到同時遷移，說明前置的都是同時執行的），就會出現問題，還是通過示意圖的方式：
怎么解決呢？
想要成功的解決競態條件問題，保證程序可以正確的按邏輯順序運行，從理論上應該滿足以下四個條件：
- 不會有兩個及以上進程同時出現在他們的critical section；
- 不要做任何關于CPU速度和數量的假設；
- 任何進程在運行到critical section之外時都不能阻塞其他進程；
- 不會有進程永遠等在critical section之前。
"Critical section" 是計算機科學中的一個概念，用于描述多個進程或線程訪問共享資源時的同步問題。在一個程序中，當多個進程或線程需要同時訪問共享資源（如共享內存或文件），為了避免數據競爭和其他同步問題，需要將訪問共享資源的代碼段限制在一個受保護的區域內，這個區域就稱為 "critical section"。在這個區域內，只有一個進程或線程可以訪問共享資源，其他進程或線程必須等待，直到進程或線程退出該區域。這樣可以確保共享資源的一致性和正確性。
為了避免這種情況的發生，我們可以采用以下幾種方法：
- 使用ConcurrentHashMap：ConcurrentHashMap是Java提供的一種線程安全的哈希表實現。它采用了分段鎖的機制，在多線程環境下能夠保證高效并發訪問。如果我們需要在多線程環境下使用哈希表，建議使用ConcurrentHashMap來代替HashMap。
- 使用Collections.synchronizedMap：Collections.synchronizedMap是Java提供的一種線程安全的Map實現。它通過對Map的所有方法進行同步，來保證線程安全。但是，由于它采用了同步的機制，因此在高并發環境下可能會出現性能瓶頸。
- 使用Lock：我們也可以使用Lock來手動控制對HashMap的訪問。具體來說，我們可以在對HashMap進行操作時，先獲取一個鎖，然后再進行操作。這種方式需要我們手動控制鎖的釋放，因此比較容易出現死鎖的情況。
