HashMap 的 Concurrency 問題

因為目前可能需要用沒有 Concurrent Package 版本的某個 HashMap 相關的 Class
所以要先整理一下 HashMap 系列的東西，在多執行緒環境下可能的問題。

在網路上搜尋這個問題時，大概都會指向同一件事：多執行緒下 HashMap 可能導致無窮迴圈。
首先可以看到 [1] 講到了使用 get() 可能會有無窮迴圈，但實際看一下，會發現無窮迴圈是來自於 HashMap 內部的 pointer 會造成內部循環
也就是 A.next() 指向 B、B.next() 指向 A，因此導致讀取時只要一進入 A、B，就會有跑不完的迴圈。

接著比較詳細的說明可以參考 [2] 或 [3]～其實兩篇說明的狀況是一樣的，只是 [2] 是中文 XD
這裡就不再解釋一次了，因為 [2-3] 都有詳細的步驟解說，還有圖示！
大意是說 HashMap 本身有兩個特性，一個是當遇到 collision 時，HashMap 會用 List 的方式把發生 collision 的 Object 全部串在一起。
也就是一般雜湊的容錯方法，當遇到兩個 Key 同時 hash 到同一個 bucket 時，就在 bucket 後面拉一串 List，把碰撞的 Key 全部串接在 bucket 後面。
另一個則是 HashMap 是用一般的陣列在處理 bucket，因此會有 bucket 不敷使用而必須延展的狀況
當需要延展時，HashMap 就需要做 rehash，把舊的所有資料一個一個重新 hash 並塞到更大的另一個陣列裡。
無窮迴圈就發生在 rehash 的階段，當兩個執行緒同時交錯著進行 rehash 時，可能會發生原本預期的 X.next() 指向的位置不是原本想像的位置
因而導致上一段說的，A.next() 指向 B、B.next() 指向 A 的悲劇。（如下圖）


圖片轉錄自 [3]

目前暫時只有看到這個問題，之前疑似有聽同事說 rehash 在多執行緒之下，好像有一個會導致陣列無限長大的問題
但不知道是同事誤解了，還是是我還沒找到那個問題的說明～。
而解決方法...現在暫時是考慮確保 HashMap 只會被一個 Thread 執行 put()、remove()，但大概需要些時間確認這樣是不是就不會有問題了。

參考資料：
1、HashMap.get() can cause an infinite loop!
2、疫苗：Java HashMap的死循环
3、A Beautiful Race Condition
4、SynchronizedMap
5、SynchronizedMap和ConcurrentHashMap的深入分析
6、无锁HashMap的原理与实现