搞懂HashTable與ConcurrentHashMap
- 前言
- 一、如何處理HashMap在多線程中的安全問題
- 二、如何實作線程安全
-
- 1.HashTable
- 2.ConcurrentHashMap
- 3.Collections.synchronizedMap(Map)
- 三、HashTable與ConcurrentHashMap get與put過程
-
- 1.HashTable的get：
- 2.HashTable的put：
- 3.ConcurrentHashMap的get：
- 4.ConcurrentHashMap的put：
- 四、1.8進行了什麼優化
- 五、ConcurrentHashMap為什麼是高并發的
- 六、CAS
-
- 1.CAS原理：
- 2.CAS防止ABA：
前言
HashMap在多線程環境下存線上程安全問題，本文将講解如何解決線程中安全問題
以下是本篇文章正文内容
一、如何處理HashMap在多線程中的安全問題
1.使用Collections.synchronizedMap(Map)建立線程安全的map集合； 2.Hashtable 3.ConcurrentHashMap 不過出于線程并發度的原因，都會舍棄前兩者使用最後的ConcurrentHashMap，他的性能和效率明顯 優于前兩者。
二、如何實作線程安全
1.HashTable
對資料操作的時候都會上鎖，導緻效率比較低下
代碼如下（示例）：每次讀寫都會加鎖 最多允許一個線程通路并發量較低
2.ConcurrentHashMap
具體原理請看 ConcurrentHashMap的put講解
1.7之前采用分段鎖的方式
1.8之後采用cas+synchronize
3.Collections.synchronizedMap(Map)
在SynchronizedMap内部維護了一個普通對象Map，還有排斥鎖mutex
建立出synchronizedMap之後，再操作map的時候，就會對方法上鎖
三、HashTable與ConcurrentHashMap get與put過程
1.HashTable的get：
首先計算key的下标,擷取hashtable中的數組
找到對應下标數組,擷取對應的連結清單
周遊倆表,判斷是否有滿足條件的entry,如果有,擷取value對應的值傳回。否則,傳回為空.
2.HashTable的put：
首先判斷value的是是否為空,如果為空,抛出空指針異常
如果不為空,擷取hashtable中的table,擷取key的hash值以及對應的下标
從數組中擷取下标對應的連結清單資訊,周遊連結清單,查詢是否有滿足條件的entry對象,如果有滿足條件的,舊值被新值覆寫,傳回舊值
如果沒有,添加一個新的entry
添加新的entry前先判斷目前數組的元素數量是否滿足擴容,如果滿足,進行擴容後,重新計算hash值和下标
然後擷取目前已經存在的entry連結清單,然後建立的entry放在原連結清單的頭部,存進數組中.
*在put方法中，如果需要向table[]中添加Entry元素，會首先進行容量校驗，如果容量已經達到了閥值，HashTable就會進行擴容處理rehash()
*預設數組的長度是11, 擴容公式(oldsize * 2 + 1), key和value不能為null
hashTable值不能為null的原因：會抛出控制原因 Hashtable使⽤的是安全失敗機制（fail-safe），這種機制會使你此次讀到的資料不一定是最新
的資料。
hashMap值能為null的原因
3.ConcurrentHashMap的get：
key通過hash定位到具體segment，在通過一次Hash定位到具體的元素上。
4.ConcurrentHashMap的put：
1.計算出hashCode值
2.判斷是否需要初始化 無初始化則調用initTable（）方法來進行初始化過程
3.檢查有無沖突，無沖突則使用cas進行儲存，失敗則進行自旋
4.判斷是否需要進行擴容
5.不滿足條件進行synchronized寫入資料
6.連結清單數量大于8進行紅黑樹轉換
7.調用addCount()統計size判斷是否擴容
四、1.8進行了什麼優化
改進一： 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table儲存資料，采用table數組元素作為鎖，進而實作了對每一行資料 進行加鎖，進 一步減少并發沖突的機率。
改進二： 将原先table數組＋單向連結清單的資料結構，變更為table數組＋單向連結清單＋紅黑樹的結構。查詢的時間複雜度可以降低到O(logN)。
JDK1.8的實作已經摒棄了Segment的概念，而是直接用Node數組+連結清單+紅黑樹的資料結構來實作，并發控制使用Synchronized和CAS來操作，整個看起來就
是優化過且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的資料結構，但是已經簡化了屬性，隻是為了相容舊版本。
初始化操作并不是在構造函數實作的，而是在put操作中實作，當然ConcurrentHashMap還提供了其他的構造函數，有指定容量大小或者指定負載因子，跟
HashMap一樣
五、ConcurrentHashMap為什麼是高并發的
1.7之前
ConcurrentHashMap 采用了分段鎖技術，其中 Segment 繼承于 ReentrantLock。
不會像 HashTable 那樣不管是 put 還是 get 操作都需要做同步處理，理論上 ConcurrentHashMap
支援CurrencyLevel (Segment 數組數量)的線程并發。
每當一個線程占用鎖通路一個 Segment 時，不會影響到其他的 Segment。
就是說如果容量大小是16他的并發度就是16，可以同時允許16個線程操作16個Segment并且還是線程安全的。
他先定位到Segment，然後再進行put操作
1.8之後
其中抛棄了原有的 Segment 分段鎖，采用了 CAS + synchronized 來保證并發安全性。
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不變，把值和next采用了volatile去修飾，保證了可用性，并且也引用了紅黑樹，在連結清單大于阈定值的時候會轉換（預設是8）。
六、CAS
1.CAS原理：
CAS 是樂觀鎖的一種實作方式，是一種輕量級鎖，JUC 中很多工具類的實作就是基于 CAS 的。
CAS 操作的流程如下圖所示，線程在讀取資料時不進行加鎖，在準備寫回資料時，比較原值是否修改，
若未被其他線程修改則寫回，若已被修改，則重新執讀讀取流程。
這是一種樂觀政策，認為并發操作并不總會發生。
2.CAS防止ABA：
一個線程把值改回了B，又來了一個線程把值改回了A，對于這個時候判斷的線程，就發現
他的值還是A，是以他就不知道這個值到底有沒有被⼈改過，其實很多場景如果隻追求最後結果正确，
這是沒關系的
解決方法
1.加版本号
2.加時間戳