Hashtable、ConcurrentHashMap源碼分析

為什么把這兩個數據結構對比分析呢，相信大家都明白。首先二者都是線程安全的，但是二者保證線程安全的方式卻是不同的。廢話不多說了，從源碼的角度分析一下兩者的異同，首先給出二者的繼承關系圖。

 Hashtable類屬性和方法源碼分析

　　我們還是先給出一張Hashtable類的屬性和方法圖，其中Entry<K,V>是Hashtable類的靜態內部類，該類繼承自Map.Entry<K,V>接口。如下將會詳細講解Hashtable類中屬性和方法的含義。

• 屬性

1. Entry<?,?>[] table ：Entry類型的數組，用于存儲Hashtable中的鍵值對；

2. int count ：存儲hashtable中有多少個鍵值對

3. int threshold ：當count值大于該值是，哈希表擴大容量，進行rehash()

4. float loadFactor ：threshold=哈希表的初始大小*loadFactor，初始容量默認為11，loadFactor值默認為0.75

5. int modCount ：實現"fail-fast"機制，在并發集合中對Hashtable進行迭代操作時，若其他線程對Hashtable進行結構性的修改，迭代器會通過比較expectedModCount和modCount是否一致，如果不一致則拋出ConcurrentModificationException異常。如下通過一個拋出ConcurrentModificationException異常的例子說明。

    ConcurrentModificationException異常

   Hashtable的remove(Object key)方法見如下方法5，每一次修改hashtable中的數據都更新modCount的值。Hashtable內部類Enumerator<T>的相關部分代碼如下：

    Enumerator類

• 方法

1. contains(Object value)，該方法是判斷該hashtable中是否含有值為value的鍵值對，執行該方法需要加鎖（synchronized）。hashtable中不允許存儲空的value，所以當查找value為空時，直接拋出空指針異常。接下來是兩個for循環遍歷table。由如上的Entry實體類中的屬性可以看出，next屬性是指向與該實體擁有相同hashcode的下一個實體。

2. containsKey(Object key)，該方法是判斷該hashtable中是否含有鍵為key的鍵值對，執行該方法也需要對整張table加鎖（synchronized）。首先根據當前給出的key值計算hashcode，并有hashcode值計算該key所在table數組中的下標，依次遍歷該下標中的每一個Entry對象e。由于不同的hashcode映射到數組中下標的位置可能相同，因此首先判斷e的hashcode值和所查詢key的hashcode值是否相同，如果相同在判斷key是否相等。

3. get(Object key)，獲取當前鍵key所對應的value值，本方法和containsKey(Object key)方法除了返回值其它都相同，如果能找到該key對應的value，則返回value的值，如果不能則返回null。

4.  put(K key, V value)，將該鍵值對加入table中。首先插入的value不能為空。其次如果當前插入的key值已經在table中存在，則用新的value替換掉原來的value值，并將原來的value值作為該方法的返回值返回。如果當前插入的key不在table中，則將該鍵值對插入。

   插入的方法首先判斷當前table中的值是否大于閾值(threshold)，如果大于該閾值，首先對該表擴容，再將新的鍵值對插入table[index]的鏈表的第一個Entry的位置上。

5. remove(Object key)，將鍵為key的Entry從table表中移除。同樣該方法也需要鎖定整個table表。如果該table中存在該鍵，則返回刪除的key的value值，如果當前table中不存在該key，則該方法的返回值為null。

6. replace(K key, V value)，將鍵為key的Entry對象值更新為value，并將原來的value最為該方法的返回值。

ConcurrentHashMap類屬性和方法源碼分析

　　ConcurrentHashMap在JDK1.8中改動還是挺大的。它摒棄了Segment（段鎖）的概念，在實現上采用了CAS算法。底層使用數組+鏈表+紅黑樹的方式，但是為了做到并發，同時也增加了大量的輔助類。如下是ConcurrentHashMap的類圖。

• 屬性

//ConcurrentHashMap最大容量private static final int MAXIMUM_CAPACITY = 1 << 30;//ConcurrentHashMap初始默認容量private static final int DEFAULT_CAPACITY = 16;//最大table數組的大小static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//默認并行級別，主體代碼并未使用private static final int DEFAULT_CONCURRENCY_LEVEL = 16;//加載因子，默認為0.75private static final float LOAD_FACTOR = 0.75f;//當hash桶中hash沖突的數目大于此值時，將鏈表轉化為紅黑樹，加快hash的查找速度static final int TREEIFY_THRESHOLD = 8;//當hash桶中hash沖突小于等于此值時，會把紅黑樹轉化為鏈表static final int UNTREEIFY_THRESHOLD = 6;//當table數組的長度大于該值時，同時滿足hash桶中hash沖突大于TREEIFY_THRESHOLD時，才會把鏈表轉化為紅黑樹static final int MIN_TREEIFY_CAPACITY = 64;//擴容操作中，transfer()方法允許多線程，該值表示一個線程執行transfer時，至少對連續的多少個hash桶進行transferprivate static final int MIN_TRANSFER_STRIDE = 16;//ForwardingNode的hash值，ForwardingNode是一種臨時節點，在擴容中才會出現，不存儲實際的數據static final int MOVED     = -1;//TreeBin的hash值，TreeBin是用于代理TreeNode的特殊節點，存儲紅黑樹的根節點static final int TREEBIN   = -2;//用于和負數hash進行&運算，將其轉化為正數static final int HASH_BITS = 0x7fffffff;

•  基本類
  

1. Node<K,V>：基本結點/普通節點。當table中的Entry以鏈表形式存儲時才使用，存儲實際數據。此類不會在ConcurrentHashMap以外被修改，而且該類的key和value永遠不為null（其子類可為null，隨后會介紹）。

    Node<K,V>

2. TreeNode：紅黑樹結點。當table中的Entry以紅黑樹的形式存儲時才會使用，存儲實際數據。ConcurrentHashMap中對TreeNode結點的操作都會由TreeBin代理執行。當滿足條件時hash會由鏈表變為紅黑樹，但是TreeNode中通過屬性prev依然保留鏈表的指針。

    TreeNode<K,V>

3. ForwardingNode：轉發結點。該節點是一種臨時結點，只有在擴容進行中才會出現，其為Node的子類，該節點的hash值固定為-1，并且他不存儲實際數據。如果舊table的一個hash桶中全部結點都遷移到新的數組中，舊table就在桶中放置一個ForwardingNode。當讀操作或者迭代操作遇到ForwardingNode時，將操作轉發到擴容后新的table數組中去執行，當寫操作遇見ForwardingNode時，則嘗試幫助擴容。

    ForwardingNode<K,V>

   補充圖一張說明擴容下是如何遍歷結點的。

4. TreeBin：代理操作TreeNode結點。該節點的hash值固定為-2，存儲實際數據的紅黑樹的根節點。因為紅黑樹進行寫入操作整個樹的結構可能發生很大變化，會影響到讀線程。因此TreeBin需要維護一個簡單的讀寫鎖，不用考慮寫-寫競爭的情況。當然并不是全部的寫操作都需要加寫鎖，只有部分put/remove需要加寫鎖。

    TreeBin<K,V>

5. ReservationNode：保留結點，也被稱為空節點。該節點的hash值固定為-3，不保存實際數據。正常的寫操作都需要對hash桶的第一個節點進行加鎖，如果hash桶的第一個節點為null時是無法加鎖的，因此需要new一個ReservationNode節點，作為hash桶的第一個節點，對該節點進行加鎖。

    ReservationNode<K,V>

• ConcurrentHashMap方法

　　首先介紹一些基本的方法，這些方法不會直接用到，但卻是理解ConcurrentHashMap常見方法前提，因為這些方法被ConcurrentHashMap常見的方法調用。然后在介紹完這些基本方法的基礎上，再分析常見的containsValue、put、remove等常見方法。

1. Node<K,V>[] initTable()：初始化table的方法。初始化這個工作不是在構造函數中執行的，而是在put方法中執行，put方法中發現table為null時，調用該方法。

    initTable方法

2. 如下幾個方法是用于讀取table數組，使用Unsafe提供更強的功能代替普通的讀寫。

    View Code

3. 擴容方法：擴容分為兩個步驟：第一步新建一個2倍大小的數組（單線程完成），第二步是rehash，把舊數組中的數據重新計算hash值放入新數組中。ConcurrentHashMap在第二步中處理舊table[index]中的節點時，這些節點要么在新table[index]處，要么在新table[index]和table[index+n]處，因此舊table各hash桶中的節點遷移不相互影響。ConcurrentHashMap擴容可以在多線程下完成，因此就需要計算每個線程需要負責處理多少個hash桶。

    計算每個transfer處理桶的個數

   計算完成之后每個transfer按照計算的值處理相應下標位置的桶，擴容操作從舊數組的末尾向前一次對hash桶進行處理。從末尾向前處理主要是減少和遍歷數據時的鎖沖突。從舊數組的末尾向前代碼如下：

    計算每個transfer處理hash桶的區域

   

   擴容部分的完整代碼如下：

    擴容代碼

   如下是一個鏈表擴容的示意圖，第一張是一個hash桶中的一條鏈表，其中藍色節點表示第X位為0，而紅色表示第X位為1，擴容后舊table[i]的桶中為一個ForwardingNode節點，而新nextTab[i]和nextTable[i+n]的桶中分別為第二張和第三張圖。

   

   

4. Traverser只讀遍歷器：確切的說它不是方法，而是一個內部類。ConcurrentHashMap的多線程擴容增加了對ConcurrentHashMap遍歷的困難。當遍歷舊table時，如果遇到某個hash桶中為ForwardingNode節點，則遍歷順序參考基本類中ForwardingNode中的介紹。

    Traverser

5. containsValue(Object value)：遍歷ConcurrentHashMap看是否存在值為value的Node。

    containsValue(Object value)

6. containsKey(Object key)：遍歷ConcurrentHashMap看是否存在鍵為key的Node。

    containsKey(Object key)

7. put(K key, V value)：將該鍵值對插入ConcurrentHashMap中。

    put(K key, V value)

8. remove(Object key)：刪除鍵為key的Node。同樣其中也包含了對replace(Object key, V value, Object cv)的介紹。

    remove(Object key)

　　至此ConcurrentHashMap的主要方法也就介紹完了，綜合比較Hashtable和ConcurrentHashMap，兩者都是線程安全的，但是Hashtable是表級鎖，而ConcurrentHashMap是段級鎖，鎖住的單個Node，而且ConcurrentHashMap可以并發讀取。對整張表進行迭代時，ConcurrentHashMap使用了不同于Hashtable的迭代方式，而是一種弱一致性的迭代器。