HashMap不安全後果及ConcurrentHashMap執行緒安全原理

Java集合HashMap不安全後果及ConcurrentHashMap 原理

HashMap

Map是我們在集合中非常重要的一個集合、我們剛學習HashMap的時候就說它不安全、可是不知道不安全會發生什麼後果

我們先來看看JDK7和JDK8當中的HashMap有什麼不一樣

JDK7 HashMap連結串列迴圈造成死迴圈

造成HasMap連結串列迴圈列表的原因就是因為在hash衝突的時候採用了頭插法且沒有加鎖的方式插入連結串列、在HashMap put的時候，put函數會檢查元素是否超出了閾值【陣列的總的新增元素數大於了 陣列長度 * 0.75(預設,也可自己設定)】，如果超出了陣列長度擴容為兩倍，下面是它擴容時將舊hash錶轉到新hash表從而完成擴容的原始碼

 /**
   * 作用：將舊陣列上的資料（鍵值對）轉移到新table中，從而完成擴容
   * 過程：按舊連結串列的正序遍歷連結串列、在新連結串列的頭部依次插入。但是這樣會導致擴容完成後，連結串列逆序
   */ 	
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //通過遍歷 舊陣列，將舊陣列上的資料（鍵值對）轉移到新陣列中
        for (Entry<K,V> e : table) {
            // 遍歷hash碰撞形成的連結串列
            while(null != e) {
                // 拿到當前頭節點的下一個節點
                Entry<K,V> next = e.next;
                // 是否要重新計算hashCode
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                 //通過hashCode計算出hash表的槽
                int i = indexFor(e.hash, newCapacity);
                // 新hash表的hash槽賦值給e 的下一個節點
                e.next = newTable[i];
                // 講當前元素，賦給新陣列的對應下標位置。
                newTable[i] = e;
                // 存取下1個Entry鏈上的元素，如此不斷迴圈，直到遍歷完該連結串列上的所有節點
                e = next;
            }
        }
    }

在單執行緒中，這樣的程式碼是沒有什麼問題，問題就是有很多個執行緒，我們假設有兩個執行緒t1和t2，他們都執行到Entry<K,V> next = e.next;這一行，此時圖示：

，t1的時間片已經用完了，t2還在繼續執行，此時t1、t2獲取的e和next分別為e1、e2、next1、next2，再之後t2完成了擴容操作，連結串列順序已經從原來的abcd變成了dcba，t1執行緒的e在next的上方，如下圖示：

此時t1執行緒醒過來了，繼續執行就會出現連結串列迴圈，造成while死迴圈

JDK8 HashMap中已經採用尾插法進行插入避免了連結串列迴圈、且連結串列長度大於8會變成紅黑樹

HashMap資料丟失

jdk7：hashMap put的時候有hash衝突如果沒有超過閾值，就會採用頭插法來插入連結串列，假如有t1和t2執行緒，它們都同時獲得了，連結串列的頭節點，此時t1執行緒的時間片沒有了，t2執行緒還在繼續，t2執行緒已經執行完了put操作，t1執行緒醒過來，t1執行緒會將自己的下一個節點指向頭節點，這樣剛剛t2執行緒put的節點就丟失了

jdk8: 採用的是尾插法、一樣的兩個執行緒都同時獲取了尾節點、後執行的那個執行緒會覆蓋掉前一個執行緒的節點、造成丟失

HashMap在官方的設定的就是執行緒不安全的，要安全選ConcurrentHashMap

JDK7 ConcurrentHashMap

在jdk7 ConcurrentHashMap當中採用了一個分段鎖的方式（Segment[]）來保證執行緒安全

Segment類繼承了ReentrantLock，Segment類裡有多個槽。

put：

計算出key在那個Segment，然後上鎖，再算出在哪個槽裡，此時如果有其它執行緒存取這個Segment會被阻塞住，直到unlock。

get：

CAS + volatile

在HashTable當中是鎖住了整個物件，執行緒t1 get("key1") 、執行緒t2 put("key2", "value2")，執行緒t2也會被阻塞住，在ConcurrentHashMap中這兩個操作是不會阻塞且不受影響。

值得注意的是Segment[]的初始長度，預設是16，不會因為資料的多少而改變，所以預設最多隻有16個執行緒獲得鎖，這個初始值可以設定，但是需要我們自己去評估多少合適。

Segment分段鎖實現下的ConcurrentHashMap的劣勢：

• 尋找元素需要經過兩次hash
• 並行級別（Segment[]長度）的合理設定問題。雖然提供了預設的並行級別，但是是否在大多數場景下都適用？歸根結底，就是需要使用者自己來評估需要多少把鎖來分段治理的問題。
• 在儲存成本比HashMap高。每個Segment管理的最少容量是2，而預設的並行級別為16，即16個Segment。假如我只需要儲存的是16個元素，那麼ConcurrentHashMap會需要佔用2倍的儲存空間。

JDK8 ConcurrentHashMap

在JDK8中，ConcurrentHashMap採用更加細粒度的鎖取消分段鎖，synchronized + CAS

put：

如果發現該槽沒有資料，初始化頭節點時，ConcurrentHashMap並沒有加鎖，而是CAS的方式進行原子替換（原子操作，基於Unsafe類的原子操作API）

如果發現該槽有資料，判斷是否正在擴容，如果是則會去幫助擴容，擴容時會進行加鎖處理，鎖定是頭節點。

如果發現該槽有節點且不在擴容，則會去鎖（synchronized）住該槽的頭節點，進行插入

get：

沒有什麼加鎖的操作，hash表被volatile修飾