Hashtable、ConcurrentHashMap源碼分析-創(chuàng)新互聯(lián)

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

成都創(chuàng)新互聯(lián)于2013年成立，先為漢陽等服務(wù)建站，漢陽等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為漢陽企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

Hashtable、ConcurrentHashMap源碼分析

 Hashtable類屬性和方法源碼分析

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

Hashtable、ConcurrentHashMap源碼分析

  • 屬性

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

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

  3. int threshold ：當(dāng)count值大于該值是，哈希表擴(kuò)大容量，進(jìn)行rehash()

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

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

    Hashtable、ConcurrentHashMap源碼分析 ConcurrentModificationException異常

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

    Hashtable、ConcurrentHashMap源碼分析 Enumerator類

  • 方法

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

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

  3. get(Object key)，獲取當(dāng)前鍵key所對應(yīng)的value值，本方法和containsKey(Object key)方法除了返回值其它都相同，如果能找到該key對應(yīng)的value，則返回value的值，如果不能則返回null。Hashtable、ConcurrentHashMap源碼分析

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

    插入的方法首先判斷當(dāng)前table中的值是否大于閾值(threshold)，如果大于該閾值，首先對該表擴(kuò)容，再將新的鍵值對插入table[index]的鏈表的第一個Entry的位置上。Hashtable、ConcurrentHashMap源碼分析

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

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

ConcurrentHashMap類屬性和方法源碼分析

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

Hashtable、ConcurrentHashMap源碼分析

  • 屬性

Hashtable、ConcurrentHashMap源碼分析

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

Hashtable、ConcurrentHashMap源碼分析

  •  基本類

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

    Hashtable、ConcurrentHashMap源碼分析 Node<K,V>

  2. TreeNode：紅黑樹結(jié)點。當(dāng)table中的Entry以紅黑樹的形式存儲時才會使用，存儲實際數(shù)據(jù)。ConcurrentHashMap中對TreeNode結(jié)點的操作都會由TreeBin代理執(zhí)行。當(dāng)滿足條件時hash會由鏈表變?yōu)榧t黑樹，但是TreeNode中通過屬性prev依然保留鏈表的指針。

    Hashtable、ConcurrentHashMap源碼分析 TreeNode<K,V>

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

    Hashtable、ConcurrentHashMap源碼分析 ForwardingNode<K,V>

    補充圖一張說明擴(kuò)容下是如何遍歷結(jié)點的。Hashtable、ConcurrentHashMap源碼分析

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

    Hashtable、ConcurrentHashMap源碼分析 TreeBin<K,V>

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

    Hashtable、ConcurrentHashMap源碼分析 ReservationNode<K,V>

  • ConcurrentHashMap方法

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

  1. Node<K,V>[] initTable()：初始化table的方法。初始化這個工作不是在構(gòu)造函數(shù)中執(zhí)行的，而是在put方法中執(zhí)行，put方法中發(fā)現(xiàn)table為null時，調(diào)用該方法。

    Hashtable、ConcurrentHashMap源碼分析 initTable方法

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

    Hashtable、ConcurrentHashMap源碼分析 View Code

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

    Hashtable、ConcurrentHashMap源碼分析 計算每個transfer處理桶的個數(shù)

    計算完成之后每個transfer按照計算的值處理相應(yīng)下標(biāo)位置的桶，擴(kuò)容操作從舊數(shù)組的末尾向前一次對hash桶進(jìn)行處理。從末尾向前處理主要是減少和遍歷數(shù)據(jù)時的鎖沖突。從舊數(shù)組的末尾向前代碼如下：

    Hashtable、ConcurrentHashMap源碼分析 計算每個transfer處理hash桶的區(qū)域

    Hashtable、ConcurrentHashMap源碼分析

    擴(kuò)容部分的完整代碼如下：

    Hashtable、ConcurrentHashMap源碼分析 擴(kuò)容代碼

    如下是一個鏈表擴(kuò)容的示意圖，第一張是一個hash桶中的一條鏈表，其中藍(lán)色節(jié)點表示第X位為0，而紅色表示第X位為1，擴(kuò)容后舊table[i]的桶中為一個ForwardingNode節(jié)點，而新nextTab[i]和nextTable[i+n]的桶中分別為第二張和第三張圖。Hashtable、ConcurrentHashMap源碼分析

    Hashtable、ConcurrentHashMap源碼分析

    Hashtable、ConcurrentHashMap源碼分析

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

    Hashtable、ConcurrentHashMap源碼分析 Traverser

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

    Hashtable、ConcurrentHashMap源碼分析 containsValue(Object value)

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

    Hashtable、ConcurrentHashMap源碼分析 containsKey(Object key)

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

    Hashtable、ConcurrentHashMap源碼分析 put(K key, V value)

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

    Hashtable、ConcurrentHashMap源碼分析 remove(Object key)

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：Hashtable、ConcurrentHashMap源碼分析-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://bm7419.com/article18/cdgodp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計、做網(wǎng)站、網(wǎng)站導(dǎo)航、用戶體驗、面包屑導(dǎo)航、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

h5響應(yīng)式網(wǎng)站建設(shè)