ConcurrentHashMap介紹

針對JDK1.8看ConcurrentHashMap是如何實(shí)現(xiàn)的

結(jié)構(gòu)圖：

目前創(chuàng)新互聯(lián)已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬主機(jī)、成都網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、濟(jì)寧網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

1、ConcurrentHashMap內(nèi)部是一個(gè)Node節(jié)點(diǎn)的數(shù)組table，數(shù)組的每一個(gè)位置table[i]代表一個(gè)桶。根據(jù)鍵的hash值映射到不同的桶內(nèi)。

transient volatile Node[] table;

2、Node節(jié)點(diǎn)一共有5種類型

1、Node節(jié)點(diǎn)，是所有節(jié)點(diǎn)的父類，可以單獨(dú)放入桶內(nèi)，也可以作為鏈表的頭放入桶內(nèi)。
2、TreeNode節(jié)點(diǎn)，繼承自Node，是紅黑樹的節(jié)點(diǎn)，此節(jié)點(diǎn)不能直接放入桶內(nèi)，只能是作為紅黑樹的節(jié)點(diǎn)。
3、TreeBin節(jié)點(diǎn)，TreeNode的代理節(jié)點(diǎn)，可以放入桶內(nèi)，這個(gè)節(jié)點(diǎn)下面可以連接紅黑樹的根節(jié)點(diǎn)，所以叫做TreeNode的代理節(jié)點(diǎn)。
4、ForwardingNode節(jié)點(diǎn)，擴(kuò)容節(jié)點(diǎn)，只是在擴(kuò)容階段使用的節(jié)點(diǎn)，當(dāng)前桶擴(kuò)容完畢后，桶內(nèi)會放入這個(gè)節(jié)點(diǎn)，此時(shí)查詢會跳轉(zhuǎn)到查詢擴(kuò)容后的table，不存儲實(shí)際數(shù)據(jù)
5、ReservationNode節(jié)點(diǎn)，內(nèi)部方法使用，暫時(shí)可以忽略。

2.1 Node節(jié)點(diǎn)

默認(rèn)桶上的結(jié)點(diǎn)就是Node結(jié)點(diǎn)。
當(dāng)出現(xiàn)hash沖突時(shí)，Node結(jié)點(diǎn)會首先以鏈表的形式鏈接到table上，當(dāng)結(jié)點(diǎn)數(shù)量超過一定數(shù)目時(shí)，鏈表會轉(zhuǎn)化為紅黑樹。因?yàn)殒湵聿檎业钠骄鶗r(shí)間復(fù)雜度為O(n)，而紅黑樹是一種平衡二叉樹，其平均時(shí)間復(fù)雜度為O(logn)。

Node只有一個(gè)next指針，是一個(gè)單鏈表，提供find方法實(shí)現(xiàn)鏈表查詢

2.2 TreeNode節(jié)點(diǎn)

TreeNode就是紅黑樹的結(jié)點(diǎn)，TreeNode不會直接鏈接到table[i]——桶上面，而是由TreeBin鏈接，TreeBin會指向紅黑樹的根結(jié)點(diǎn)。

提供了基于樹查找的findTreeNode方法。

2.3 TreeBin節(jié)點(diǎn)

TreeBin會直接鏈接到table[i]——桶上面，該結(jié)點(diǎn)提供了一系列紅黑樹相關(guān)的操作，以及加鎖、解鎖操作。

另外TreeBin提供了一系列的操作
1、TreeBin(TreeNode b)，將以b為頭結(jié)點(diǎn)的鏈表轉(zhuǎn)換為紅黑樹.
2、lockRoot()，對紅黑樹的根結(jié)點(diǎn)加寫鎖
3、unlockRoot()，釋放寫鎖
4、find(int h, Object k)，從根結(jié)點(diǎn)開始遍歷查找，找到“相等”的結(jié)點(diǎn)就返回它，沒找到就返回null，當(dāng)存在寫鎖時(shí)，以鏈表方式進(jìn)行查找，不阻塞讀鎖。

5、removeTreeNode(TreeNode p)，刪除紅黑樹的結(jié)點(diǎn)

a、紅黑樹規(guī)模太小時(shí)，返回true，然后進(jìn)行 樹 -> 鏈表 的轉(zhuǎn)化
b、紅黑樹規(guī)模足夠時(shí)，不用變換成鏈表，但刪除結(jié)點(diǎn)時(shí)需要加寫鎖

6、紅黑樹的左旋，右旋等一系列算法。

2.4 ForwardingNode節(jié)點(diǎn)

1、ForwardingNode是一種臨時(shí)結(jié)點(diǎn)，在擴(kuò)容進(jìn)行中才會出現(xiàn)，hash值固定為-1，且不存儲實(shí)際數(shù)據(jù)。
2、如果舊table數(shù)組的一個(gè)hash桶中全部的結(jié)點(diǎn)都遷移到了新table中，則在這個(gè)桶中放置一個(gè)ForwardingNode。
3、讀操作碰到ForwardingNode時(shí)，將操作轉(zhuǎn)發(fā)到擴(kuò)容后的新table數(shù)組上去執(zhí)行；寫操作碰見它時(shí)，則嘗試幫助擴(kuò)容，擴(kuò)容是支持多線程一起擴(kuò)容的。
4、提供了在新的數(shù)組nextTable上進(jìn)行查找的方法find

2.5 ReservationNode節(jié)點(diǎn)

1、保留結(jié)點(diǎn).
2、hash值固定為-3， 不保存實(shí)際數(shù)據(jù)
3、只在computeIfAbsent和compute這兩個(gè)函數(shù)式API中充當(dāng)占位符加鎖使用

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

新聞標(biāo)題：多線程（十四、ConcurrentHashMap原理（1）節(jié)點(diǎn)）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://www.weahome.cn/article/csseph.html