為什么把這兩個(gè)數(shù)據(jù)結(jié)構(gòu)對(duì)比分析呢，相信大家都明白。首先二者都是線程安全的，但是二者保證線程安全的方式卻是不同的。廢話不多說了，從源碼的角度分析一下兩者的異同，首先給出二者的繼承關(guān)系圖。
成都創(chuàng)新互聯(lián)于2013年成立，先為漢陽等服務(wù)建站，漢陽等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為漢陽企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
我們還是先給出一張Hashtable類的屬性和方法圖，其中Entry
屬性
Entry[] table ：Entry類型的數(shù)組，用于存儲(chǔ)Hashtable中的鍵值對(duì)；
int count ：存儲(chǔ)hashtable中有多少個(gè)鍵值對(duì)
int threshold ：當(dāng)count值大于該值是，哈希表擴(kuò)大容量，進(jìn)行rehash()
float loadFactor ：threshold=哈希表的初始大小*loadFactor，初始容量默認(rèn)為11，loadFactor值默認(rèn)為0.75
int modCount ：實(shí)現(xiàn)"fail-fast"機(jī)制，在并發(fā)集合中對(duì)Hashtable進(jìn)行迭代操作時(shí)，若其他線程對(duì)Hashtable進(jìn)行結(jié)構(gòu)性的修改，迭代器會(huì)通過比較expectedModCount和modCount是否一致，如果不一致則拋出ConcurrentModificationException異常。如下通過一個(gè)拋出ConcurrentModificationException異常的例子說明。
ConcurrentModificationException異常
Hashtable的remove(Object key)方法見如下方法5，每一次修改hashtable中的數(shù)據(jù)都更新modCount的值。Hashtable內(nèi)部類Enumerator
Enumerator類
方法
contains(Object value)，該方法是判斷該hashtable中是否含有值為value的鍵值對(duì)，執(zhí)行該方法需要加鎖（synchronized）。hashtable中不允許存儲(chǔ)空的value，所以當(dāng)查找value為空時(shí)，直接拋出空指針異常。接下來是兩個(gè)for循環(huán)遍歷table。由如上的Entry實(shí)體類中的屬性可以看出，next屬性是指向與該實(shí)體擁有相同hashcode的下一個(gè)實(shí)體。
containsKey(Object key)，該方法是判斷該hashtable中是否含有鍵為key的鍵值對(duì)，執(zhí)行該方法也需要對(duì)整張table加鎖（synchronized）。首先根據(jù)當(dāng)前給出的key值計(jì)算hashcode，并有hashcode值計(jì)算該key所在table數(shù)組中的下標(biāo)，依次遍歷該下標(biāo)中的每一個(gè)Entry對(duì)象e。由于不同的hashcode映射到數(shù)組中下標(biāo)的位置可能相同，因此首先判斷e的hashcode值和所查詢key的hashcode值是否相同，如果相同在判斷key是否相等。
get(Object key)，獲取當(dāng)前鍵key所對(duì)應(yīng)的value值，本方法和containsKey(Object key)方法除了返回值其它都相同，如果能找到該key對(duì)應(yīng)的value，則返回value的值，如果不能則返回null。
put(K key, V value)，將該鍵值對(duì)加入table中。首先插入的value不能為空。其次如果當(dāng)前插入的key值已經(jīng)在table中存在，則用新的value替換掉原來的value值，并將原來的value值作為該方法的返回值返回。如果當(dāng)前插入的key不在table中，則將該鍵值對(duì)插入。
插入的方法首先判斷當(dāng)前table中的值是否大于閾值(threshold)，如果大于該閾值，首先對(duì)該表擴(kuò)容，再將新的鍵值對(duì)插入table[index]的鏈表的第一個(gè)Entry的位置上。
remove(Object key)，將鍵為key的Entry從table表中移除。同樣該方法也需要鎖定整個(gè)table表。如果該table中存在該鍵，則返回刪除的key的value值，如果當(dāng)前table中不存在該key，則該方法的返回值為null。
replace(K key, V value)，將鍵為key的Entry對(duì)象值更新為value，并將原來的value最為該方法的返回值。
ConcurrentHashMap在JDK1.8中改動(dòng)還是挺大的。它摒棄了Segment（段鎖）的概念，在實(shí)現(xiàn)上采用了CAS算法。底層使用數(shù)組+鏈表+紅黑樹的方式，但是為了做到并發(fā)，同時(shí)也增加了大量的輔助類。如下是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)并行級(jí)別，主體代碼并未使用private static final int DEFAULT_CONCURRENCY_LEVEL = 16;//加載因子，默認(rèn)為0.75private static final float LOAD_FACTOR = 0.75f;//當(dāng)hash桶中hash沖突的數(shù)目大于此值時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，加快hash的查找速度static final int TREEIFY_THRESHOLD = 8;//當(dāng)hash桶中hash沖突小于等于此值時(shí)，會(huì)把紅黑樹轉(zhuǎn)化為鏈表static final int UNTREEIFY_THRESHOLD = 6;//當(dāng)table數(shù)組的長(zhǎng)度大于該值時(shí)，同時(shí)滿足hash桶中hash沖突大于TREEIFY_THRESHOLD時(shí)，才會(huì)把鏈表轉(zhuǎn)化為紅黑樹static final int MIN_TREEIFY_CAPACITY = 64;//擴(kuò)容操作中，transfer()方法允許多線程，該值表示一個(gè)線程執(zhí)行transfer時(shí)，至少對(duì)連續(xù)的多少個(gè)hash桶進(jìn)行transferprivate static final int MIN_TRANSFER_STRIDE = 16;//ForwardingNode的hash值，F(xiàn)orwardingNode是一種臨時(shí)節(jié)點(diǎn)，在擴(kuò)容中才會(huì)出現(xiàn)，不存儲(chǔ)實(shí)際的數(shù)據(jù)static final int MOVED = -1;//TreeBin的hash值，TreeBin是用于代理TreeNode的特殊節(jié)點(diǎn)，存儲(chǔ)紅黑樹的根節(jié)點(diǎn)static final int TREEBIN = -2;//用于和負(fù)數(shù)hash進(jìn)行&運(yùn)算，將其轉(zhuǎn)化為正數(shù)static final int HASH_BITS = 0x7fffffff;
基本類
Node
Node
TreeNode：紅黑樹結(jié)點(diǎn)。當(dāng)table中的Entry以紅黑樹的形式存儲(chǔ)時(shí)才會(huì)使用，存儲(chǔ)實(shí)際數(shù)據(jù)。ConcurrentHashMap中對(duì)TreeNode結(jié)點(diǎn)的操作都會(huì)由TreeBin代理執(zhí)行。當(dāng)滿足條件時(shí)hash會(huì)由鏈表變?yōu)榧t黑樹，但是TreeNode中通過屬性prev依然保留鏈表的指針。
TreeNode
ForwardingNode：轉(zhuǎn)發(fā)結(jié)點(diǎn)。該節(jié)點(diǎn)是一種臨時(shí)結(jié)點(diǎn)，只有在擴(kuò)容進(jìn)行中才會(huì)出現(xiàn)，其為Node的子類，該節(jié)點(diǎn)的hash值固定為-1，并且他不存儲(chǔ)實(shí)際數(shù)據(jù)。如果舊table的一個(gè)hash桶中全部結(jié)點(diǎn)都遷移到新的數(shù)組中，舊table就在桶中放置一個(gè)ForwardingNode。當(dāng)讀操作或者迭代操作遇到ForwardingNode時(shí)，將操作轉(zhuǎn)發(fā)到擴(kuò)容后新的table數(shù)組中去執(zhí)行，當(dāng)寫操作遇見ForwardingNode時(shí)，則嘗試幫助擴(kuò)容。
ForwardingNode
補(bǔ)充圖一張說明擴(kuò)容下是如何遍歷結(jié)點(diǎn)的。
TreeBin：代理操作TreeNode結(jié)點(diǎn)。該節(jié)點(diǎn)的hash值固定為-2，存儲(chǔ)實(shí)際數(shù)據(jù)的紅黑樹的根節(jié)點(diǎn)。因?yàn)榧t黑樹進(jìn)行寫入操作整個(gè)樹的結(jié)構(gòu)可能發(fā)生很大變化，會(huì)影響到讀線程。因此TreeBin需要維護(hù)一個(gè)簡(jiǎn)單的讀寫鎖，不用考慮寫-寫競(jìng)爭(zhēng)的情況。當(dāng)然并不是全部的寫操作都需要加寫鎖，只有部分put/remove需要加寫鎖。
TreeBin
ReservationNode：保留結(jié)點(diǎn)，也被稱為空節(jié)點(diǎn)。該節(jié)點(diǎn)的hash值固定為-3，不保存實(shí)際數(shù)據(jù)。正常的寫操作都需要對(duì)hash桶的第一個(gè)節(jié)點(diǎn)進(jìn)行加鎖，如果hash桶的第一個(gè)節(jié)點(diǎn)為null時(shí)是無法加鎖的，因此需要new一個(gè)ReservationNode節(jié)點(diǎn)，作為hash桶的第一個(gè)節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)進(jìn)行加鎖。
ReservationNode
ConcurrentHashMap方法
首先介紹一些基本的方法，這些方法不會(huì)直接用到，但卻是理解ConcurrentHashMap常見方法前提，因?yàn)檫@些方法被ConcurrentHashMap常見的方法調(diào)用。然后在介紹完這些基本方法的基礎(chǔ)上，再分析常見的containsValue、put、remove等常見方法。
Node
initTable方法
如下幾個(gè)方法是用于讀取table數(shù)組，使用Unsafe提供更強(qiáng)的功能代替普通的讀寫。
View Code
擴(kuò)容方法：擴(kuò)容分為兩個(gè)步驟：第一步新建一個(gè)2倍大小的數(shù)組（單線程完成），第二步是rehash，把舊數(shù)組中的數(shù)據(jù)重新計(jì)算hash值放入新數(shù)組中。ConcurrentHashMap在第二步中處理舊table[index]中的節(jié)點(diǎn)時(shí)，這些節(jié)點(diǎn)要么在新table[index]處，要么在新table[index]和table[index+n]處，因此舊table各hash桶中的節(jié)點(diǎn)遷移不相互影響。ConcurrentHashMap擴(kuò)容可以在多線程下完成，因此就需要計(jì)算每個(gè)線程需要負(fù)責(zé)處理多少個(gè)hash桶。
計(jì)算每個(gè)transfer處理桶的個(gè)數(shù)
計(jì)算完成之后每個(gè)transfer按照計(jì)算的值處理相應(yīng)下標(biāo)位置的桶，擴(kuò)容操作從舊數(shù)組的末尾向前一次對(duì)hash桶進(jìn)行處理。從末尾向前處理主要是減少和遍歷數(shù)據(jù)時(shí)的鎖沖突。從舊數(shù)組的末尾向前代碼如下：
計(jì)算每個(gè)transfer處理hash桶的區(qū)域
擴(kuò)容部分的完整代碼如下：
擴(kuò)容代碼
如下是一個(gè)鏈表擴(kuò)容的示意圖，第一張是一個(gè)hash桶中的一條鏈表，其中藍(lán)色節(jié)點(diǎn)表示第X位為0，而紅色表示第X位為1，擴(kuò)容后舊table[i]的桶中為一個(gè)ForwardingNode節(jié)點(diǎn)，而新nextTab[i]和nextTable[i+n]的桶中分別為第二張和第三張圖。
Traverser只讀遍歷器：確切的說它不是方法，而是一個(gè)內(nèi)部類。ConcurrentHashMap的多線程擴(kuò)容增加了對(duì)ConcurrentHashMap遍歷的困難。當(dāng)遍歷舊table時(shí)，如果遇到某個(gè)hash桶中為ForwardingNode節(jié)點(diǎn)，則遍歷順序參考基本類中ForwardingNode中的介紹。
Traverser
containsValue(Object value)：遍歷ConcurrentHashMap看是否存在值為value的Node。
containsValue(Object value)
containsKey(Object key)：遍歷ConcurrentHashMap看是否存在鍵為key的Node。
containsKey(Object key)
put(K key, V value)：將該鍵值對(duì)插入ConcurrentHashMap中。
put(K key, V value)
remove(Object key)：刪除鍵為key的Node。同樣其中也包含了對(duì)replace(Object key, V value, Object cv)的介紹。
remove(Object key)
至此ConcurrentHashMap的主要方法也就介紹完了，綜合比較Hashtable和ConcurrentHashMap，兩者都是線程安全的，但是Hashtable是表級(jí)鎖，而ConcurrentHashMap是段級(jí)鎖，鎖住的單個(gè)Node，而且ConcurrentHashMap可以并發(fā)讀取。對(duì)整張表進(jìn)行迭代時(shí)，ConcurrentHashMap使用了不同于Hashtable的迭代方式，而是一種弱一致性的迭代器。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
