并發(fā)情況的哈希表

前文中 JDK容器三大將之--哈希表（HashMap） 提到過(guò)哈希表，Java中單線程情況時(shí)采用了HashMap這樣的數(shù)據(jù)結(jié)構(gòu)通過(guò)對(duì)數(shù)組的封裝實(shí)現(xiàn)了哈希表數(shù)據(jù)結(jié)構(gòu)，并且被各個(gè)軟件廣泛使用，也提到過(guò)HashMap的modCount字段用來(lái)對(duì)并發(fā)情況拋出快速失敗西疤。
既然HashMap不支持并發(fā)的讀取和修改放钦，那么肯定需要另外一種數(shù)據(jù)結(jié)構(gòu)來(lái)提供保證線程安全的哈希表結(jié)構(gòu)结窘，筆者了解到的有三種方式赖条。

• HashTable如孝，通過(guò)對(duì)put/get等方法加鎖實(shí)現(xiàn)互斥功能
• Collections.synchronizedMap(map)宪哩，通過(guò)調(diào)用JDK提供的方法將已有的HashMap封裝為支持并發(fā)的SynchronizedMap（裝飾器模式），本質(zhì)上和HashTable比較類似
• ConcurrentHashMap

其中 HashTable 和 Collections.synchronizedMap(map)方法生成的SynchronizedMap 都是簡(jiǎn)單粗暴的對(duì)put/get方法加上了synchronized鎖來(lái)控制線程安全第晰，
例如：有一個(gè)哈希表map锁孟，先后有三個(gè)線程分別執(zhí)行了put(1,1), put(1,2), put(10086,666)的請(qǐng)求，那么這三個(gè)操作只能夠順序執(zhí)行茁瘦，如下圖所示

hashtable鎖全表

ConcurrentHashMap

ConcurrentHashMap各個(gè)變量介紹

• table腔稀，是一個(gè)Node[]數(shù)組盆昙，同HashMap一樣，通過(guò)數(shù)組+拉鏈法存儲(chǔ)實(shí)際的value數(shù)據(jù)
• nextTable焊虏，一般為null淡喜，只有在ConcurrentHashMap執(zhí)行resize遷移的時(shí)候有值
• baseCount，沒(méi)有鎖競(jìng)爭(zhēng)時(shí)直接返回該哈希表的大小
• sizeCtl诵闭，控制table的初始化和resize狀態(tài)炼团，
  • -1，初始化中
  • -(1+活躍中的resize任務(wù)個(gè)數(shù))疏尿，存儲(chǔ)擴(kuò)容中的任務(wù)個(gè)數(shù)
  • table為null瘟芝，保存table將來(lái)進(jìn)行第一次初始化時(shí)的大小
  • table已經(jīng)初始化成功后，保存著下一次擴(kuò)容的目標(biāo)大小
• transferIndex润歉，下次擴(kuò)容需要從table該下標(biāo)開(kāi)始分裂
• cellsBusy模狭，擴(kuò)容和計(jì)數(shù)時(shí)需要用到的自旋鎖
• counterCells，CounterCell[]數(shù)組踩衩，CounterCell是基于LongAdder改造的用于多線程計(jì)數(shù)功能的實(shí)現(xiàn)嚼鹉，LongAdder也是AtomicLong的底層實(shí)現(xiàn)

put()方法的實(shí)現(xiàn)與分段鎖

ConcurrentHashMap的put過(guò)程偽代碼可以描述為如下

def put(key, value):
    hash = hash(key) # 根據(jù)key計(jì)算hash
    if table == null: # 1.table為空時(shí)初始化
        table = initTable() # 初始化后重新嘗試獲取key
    if table != null and table[hash] == null: # 2.table不空 且 key所在的桶尚沒(méi)有值，則通過(guò)cas存入值
        casTabAt(table, hash, key, value)
    if table != null and table[hash] == MOVED: # 3.table不空 且 key所在位置標(biāo)識(shí)為遷移中驱富，則執(zhí)行helpTransfer幫助遷移
        table = helpTransfer(table, table[hash]) # 遷移后重新嘗試獲取key
    if table != null and table[hash] != MOVED: # 4.table不空 且 key所在位置有哈希沖突锚赤，則對(duì)該段加鎖執(zhí)行傳統(tǒng)HashMap的拉鏈法+紅黑樹(shù)處理邏輯
        hashCollisionWithSynchronized(table, hash, key, value)
    addCount(1, binCount) # hash節(jié)點(diǎn)數(shù)+1

put操作的整個(gè)流程如下

put操作過(guò)程流程圖

下面依次詳細(xì)介紹initTable、casTabAt褐鸥、helpTransfer方法的執(zhí)行過(guò)程线脚，拉鏈法+紅黑樹(shù)的哈希沖突處理方式除了加了synchronized鎖和double-check功能之外與普通HashMap區(qū)別不大，本文就不再贅述了，感興趣的讀者可以從HashMap的哈希沖突處理了解浑侥。

（和上圖對(duì)比下同樣put操作的流程）

initTable--并發(fā)情況下table的初始化(CAS)

當(dāng)table數(shù)組為空的時(shí)候姊舵，會(huì)調(diào)用initTable方法初始化table數(shù)組，這里用到了上文提到的ConcurrentHashMap的變量sizeCtl寓落，方法的代碼并不長(zhǎng)括丁，這里就不再貼了，方法執(zhí)行的流程如下

initTable流程

Java中通過(guò) sun.misc.Unsafe#compareAndSwapInt的native方法實(shí)現(xiàn)cas的調(diào)用（系統(tǒng)調(diào)用保證比較和替換操作的原子性）
方法的作用是伶选，讀取傳入對(duì)象o在內(nèi)存中偏移量為offset位置的值與期望值expected作比較史飞。
相等就把x值賦值給offset位置的值。方法返回true仰税。
不相等构资，就取消賦值，方法返回false陨簇。
這也是CAS的思想吐绵，即比較并交換。用于保證并發(fā)時(shí)的無(wú)鎖并發(fā)的安全性塞帐。

casTabAt--cas樂(lè)觀鎖

調(diào)用的是 sun.misc.Unsafe#compareAndSwapObject
compareAndSwapXXX接收四個(gè)參數(shù)拦赠，分別是

• 要被進(jìn)行swap操作的對(duì)象
• 偏移量
• expect
• 目標(biāo)value

該方法是native調(diào)用，系統(tǒng)調(diào)用保證了比較和替換過(guò)程的原子性葵姥。CAS是Java樂(lè)觀鎖的實(shí)現(xiàn)方式荷鼠，樂(lè)觀鎖，顧名思義榔幸，是假設(shè)有很大概率能夠獲得鎖而產(chǎn)生的邏輯允乐，樂(lè)觀鎖的本質(zhì)即 自旋的while循環(huán) + CAS操作，搶不到就繼續(xù)自旋削咆。

helpTransfer--ConcurrentHashMap的擴(kuò)容過(guò)程

helpTransfer的擴(kuò)容過(guò)程詳細(xì)邏輯涉及到ConcurrentHashMap出于對(duì)硬件性能的考慮牍疏，代碼的實(shí)現(xiàn)比較晦澀難懂，本文會(huì)屏蔽掉這些數(shù)學(xué)計(jì)算的詳細(xì)細(xì)節(jié)拨齐，旨在大體介紹下ConcurrentHashMap的擴(kuò)容過(guò)程鳞陨。
helpTransfer方法的偽代碼如下

def helpTransfer(table, f): # table即ConcurrentHashMap的舊table[]數(shù)組，f即上文的ForwardingNode
    if table != null and f instanceof ForwardingNode: # 經(jīng)典double-check
        while(f.nextTable == this.nextTable and this.table == table and sizeCtl < 0): # 還是double-check
            if noNeedMoreHelperThread(sizeCtl): # 判斷幫助遷移的線程不需要人手了瞻惋，返回
                return
            if cas(this, sizeCtl, sizeCtl+1): # cas操作sizeCtl厦滤，準(zhǔn)備幫忙
                transfer(table, nextTable) # 具體的遷移過(guò)程
                return
            # 需要幫忙，但是cas沒(méi)搶到歼狼，自旋

可以看到helpTransfer方法的主要作用是判斷遷移工作還需不需要自己參與掏导，這個(gè)是根據(jù)sizeCtl和table.length計(jì)算得到的，讀者可以自己深追細(xì)節(jié)羽峰。接下來(lái)就是遷移過(guò)程的核心方法transfer趟咆，偽代碼如下：

def transfer(table, nextTable):
    stride = calcStride(table.length) # 根據(jù)當(dāng)前CPU核數(shù)和舊table大小計(jì)算【跨度】
    if nextTable == null:
        nextTable = new Node[n << 1] # 擴(kuò)容一倍
    advance = true # advance是一個(gè)狀態(tài)標(biāo)識(shí)添瓷，可以理解為【攬活中】
    for():
        while(advance):
            if transfering() || finishing:
                advance = false # 如果正在遷移中或者遷移結(jié)束了，不需要再攬活
            else
                bound, i = calcBoundByCas(transferIndex, stride) # 通過(guò)transferIndex變量和前面算出來(lái)的跨度值纱，計(jì)算出當(dāng)前要攬活多少鳞贷，table[bound -> i]
                advance = fasle # 攬活結(jié)束，開(kāi)始干活
        if noMoreTodo():
            doFinish() # 通過(guò)下標(biāo)判斷沒(méi)有更多任務(wù)了虐唠，則進(jìn)行收尾工作
            return # 退出悄晃，這里是出口
        if hasMoreTodo() and tabAt(table, i) == null:
            casTabAt(table, i, null, fwd) # 置為fwd節(jié)點(diǎn)
            continue # 繼續(xù)for循環(huán)
        if hasMoreTodo() and tabAt(table, i) == MOVED: # 已經(jīng)是fwd節(jié)點(diǎn)
            advance=true # 說(shuō)明別的線程在施工，循環(huán)重新攬活
            continue # 繼續(xù)for循環(huán)
        if hasMoreTodo() and tableAt(table, i) != MOVED: # 普通節(jié)點(diǎn)
            transferSynchronized()  # synchronized加鎖執(zhí)行遷移凿滤，遷移的過(guò)程中也會(huì)將施工中的節(jié)點(diǎn)置為fwd節(jié)點(diǎn)，遷移細(xì)節(jié)和普通HashMap一樣庶近，大致就是根據(jù)節(jié)點(diǎn)的hash值算出low和high翁脆，然后分別落到新table的不同索引位置
        

幾個(gè)概念

• stride，跨度鼻种，根據(jù)硬件性能評(píng)估出每個(gè)線程一批能處理多少范圍的桶
• advance模式反番，攬活模式，這時(shí)候正在算當(dāng)前線程要處理table[bound, i]的遷移工作
• finishing模式叉钥，收尾工作罢缸，table置為nextTable，nextTable置為null投队，sizeCtl賦值

整個(gè)擴(kuò)容過(guò)程的執(zhí)行模式如下圖

多線程擴(kuò)容過(guò)程

節(jié)點(diǎn)可能的狀態(tài)：

• 普通節(jié)點(diǎn)枫疆，沒(méi)有進(jìn)行遷移時(shí)的普通節(jié)點(diǎn)，分為拉鏈節(jié)點(diǎn)敷鸦、紅黑樹(shù)節(jié)點(diǎn)

• 路由節(jié)點(diǎn)ForwardingNode息楔，在遷移中狀態(tài)時(shí)安放在舊table上的特殊節(jié)點(diǎn)，用作路由

  
  
  施工中

路由節(jié)點(diǎn)ForwardingNode

與單線程的HashMap不同的是扒披，多線程的ConcurrentHashMap的遷移過(guò)程必須要考慮到遷移過(guò)程中有其它線程的讀操作值依，因此我們只能有兩種選擇：

1. 在遷移的過(guò)程中將整個(gè)表鎖住，所有讀取的操作都因?yàn)榈孺i而掛起碟案，這種方式性能上是不可接受的
2. 在遷移的過(guò)程中愿险，一定會(huì)存在部分桶遷完了、部分桶沒(méi)遷完的中間狀態(tài)价说，在這種狀態(tài)下進(jìn)行g(shù)et辆亏、put操作時(shí)，為了能夠保證遷移完的都走新table熔任，就因此產(chǎn)生了ForwardingNode節(jié)點(diǎn)的概念褒链，大致流程如下圖所示（注意在某個(gè)桶的遷移過(guò)程中還是通過(guò)synchronized加鎖了的，這和我們前面討論的分段鎖的用法是一致的）
   
   forward

addCount--ConcurrentHashMap的size()方法與LongAdder

addCount

ConcurrentHashMap的addCount方法的實(shí)現(xiàn)借鑒了LongAdder的實(shí)現(xiàn)原理疑苔，大致可以粗略理解為：

• 如果沒(méi)有發(fā)現(xiàn)競(jìng)爭(zhēng)（通過(guò)CAS）甫匹，返回 baseCount + x（很簡(jiǎn)單的 baseCount+=x）
• 如果發(fā)現(xiàn)競(jìng)爭(zhēng)，采用了類似分段鎖的思想，根據(jù)當(dāng)前線程的hash定位到了CounterCell[index]兵迅，然后通過(guò)CAS給這個(gè)CounterCell累加（有ConcurrentHashMap分段鎖那味了）抢韭，最后獲取總數(shù)時(shí)是 baseCount + cells[0-n]

以下是大致實(shí)現(xiàn)流程圖，本文沒(méi)有深入實(shí)現(xiàn)的細(xì)節(jié)（例如CounterCell數(shù)組初始化恍箭、擴(kuò)容等）刻恭，想要深入了解的讀者可以參考這篇文章 深入剖析LongAdder是咋干活的，寫的挺好的

image

ConcurrentHashMap的size()方法

基于上面第LongAdder的大致實(shí)現(xiàn)原理的理解扯夭，size方法的流程可以直接貼源碼了
sum = baseCount + counterCells[0] + counterCells[1] + ... + counterCells[n]

    final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

從源碼可以看到鳍贾，ConcurrentHashMap的size()方法不能保證結(jié)果的完全準(zhǔn)確，這個(gè)方法完全沒(méi)有加鎖交洗，也就是baseCount骑科、counterCells[i]都有可能被并發(fā)修改，但是如果執(zhí)行sumCount的時(shí)候加鎖會(huì)影響性能构拳，這也是犧牲準(zhǔn)確性換取性能的一種折衷吧

總結(jié)

從源碼中可以看出咆爽，Java為了最大能力的優(yōu)化哈希表在并發(fā)情況下的性能盡可能做了最大的努力，包括：

• 鎖是避免不了的置森，但是鎖住的數(shù)據(jù)量要盡可能的少（少鎖住點(diǎn)） -- 分段鎖
• 在一些不太可能出現(xiàn)競(jìng)爭(zhēng)斗埂，只是不加鎖又有可能會(huì)有線程安全風(fēng)險(xiǎn)的地方，盡量使用CAS樂(lè)觀鎖凫海，不要掛起線程（能別鎖就別鎖）
• 在put等操作時(shí)發(fā)現(xiàn)正在遷移的過(guò)程中呛凶，順便一起幫幫忙，可以盐碱，這很團(tuán)結(jié)

只能說(shuō)不愧是你把兔，Doug Lea。

Reference

[1] 《Java并發(fā)編程實(shí)戰(zhàn)》
[2] JDK容器三大將之--哈希表（HashMap）
[3] 深入剖析LongAdder是咋干活的