在《疫苗：Java HashMap的死循環(huán)》中，我們看到，java.util.HashMap并不能直接應(yīng)用于多線程環(huán)境。對(duì)于多線程環(huán)境中應(yīng)用HashMap，主要有以下幾種選擇：

1. 使用線程安全的java.util.Hashtable作為替代​
2. 使用java.util.Collections.synchronizedMap方法，將已有的HashMap對(duì)象包裝為線程安全的。
3. 使用java.util.concurrent.ConcurrentHashMap類作為替代，它具有非常好的性能。

而以上幾種方法在實(shí)現(xiàn)的具體細(xì)節(jié)上，都或多或少地用到了互斥鎖。互斥鎖會(huì)造成線程阻塞，降低運(yùn)行效率，并有可能產(chǎn)生死鎖、優(yōu)先級(jí)翻轉(zhuǎn)等一系列問(wèn)題。

CAS(Compare And Swap)是一種底層硬件提供的功能，它可以將判斷并更改一個(gè)值的操作原子化。關(guān)于CAS的一些應(yīng)用，《無(wú)鎖隊(duì)列的實(shí)現(xiàn)》一文中有很詳細(xì)的介紹。

Java中的原子操作

在java.util.concurrent.atomic包中，Java為我們提供了很多方便的原子類型，它們底層完全基于CAS操作。

例如我們希望實(shí)現(xiàn)一個(gè)全局公用的計(jì)數(shù)器，那么可以：

privateAtomicInteger counter =newAtomicInteger(3); 
 
publicvoidaddCounter() { 
 
    for(;;) { 
 
        intoldValue = counter.get(); 
 
        intnewValue = oldValue +1; 
 
        if(counter.compareAndSet(oldValue, newValue)) 
 
            return; 
 
    } 
 
} 

其中，compareAndSet方法會(huì)檢查counter現(xiàn)有的值是否為oldValue，如果是，則將其設(shè)置為新值newValue，操作成功并返回true；否則操作失敗并返回false。

當(dāng)計(jì)算counter新值時(shí)，若其他線程將counter的值改變，compareAndSwap就會(huì)失敗。此時(shí)我們只需在外面加一層循環(huán)，不斷嘗試這個(gè)過(guò)程，那么最終一定會(huì)成功將counter值+1。（其實(shí)AtomicInteger已經(jīng)為常用的+1/-1操作定義了 incrementAndGet與decrementAndGet方法，以后我們只需簡(jiǎn)單調(diào)用它即可）

除了AtomicInteger外，java.util.concurrent.atomic包還提供了AtomicReference和AtomicReferenceArray類型，它們分別代表原子性的引用和原子性的引用數(shù)組（引用的數(shù)組）。

無(wú)鎖鏈表的實(shí)現(xiàn)

在實(shí)現(xiàn)無(wú)鎖HashMap之前，讓我們先來(lái)看一下比較簡(jiǎn)單的無(wú)鎖鏈表的實(shí)現(xiàn)方法。

以插入操作為例：

1. 首先我們需要找到待插入位置前面的節(jié)點(diǎn)A和后面的節(jié)點(diǎn)B。
2. 然后新建一個(gè)節(jié)點(diǎn)C，并使其next指針指向節(jié)點(diǎn)B。（見(jiàn)圖1）
3. ***使節(jié)點(diǎn)A的next指針指向節(jié)點(diǎn)C。（見(jiàn)圖2）

但在操作中途，有可能其他線程在A與B直接也插入了一些節(jié)點(diǎn)（假設(shè)為D），如果我們不做任何判斷，可能造成其他線程插入節(jié)點(diǎn)的丟失。（見(jiàn)圖3）我們可以利用CAS操作，在為節(jié)點(diǎn)A的next指針賦值時(shí)，判斷其是否仍然指向B，如果節(jié)點(diǎn)A的next指針發(fā)生了變化則重試整個(gè)插入操作。大致代碼如下：

privatevoidlistInsert(Node head, Node c) { 
 
 
    for(;;) { 
 
 
        Node a = findInsertionPlace(head), b = a.next.get(); 
 
 
        c.next.set(b); 
 
        if(a.next.compareAndSwap(b,c)) 
 
            return; 
    } 
} 

(Node類的next字段為AtomicReference<Node>類型，即指向Node類型的原子性引用)

無(wú)鎖鏈表的查找操作與普通鏈表沒(méi)有區(qū)別。而其刪除操作，則需要找到待刪除節(jié)點(diǎn)前方的節(jié)點(diǎn)A和后方的節(jié)點(diǎn)B，利用CAS操作驗(yàn)證并更新節(jié)點(diǎn)A的next指針，使其指向節(jié)點(diǎn)B。

無(wú)鎖HashMap的難點(diǎn)與突破

HashMap主要有插入、刪除、查找以及ReHash四種基本操作。一個(gè)典型的HashMap實(shí)現(xiàn)，會(huì)用到一個(gè)數(shù)組，數(shù)組的每項(xiàng)元素為一個(gè)節(jié)點(diǎn)的鏈表。對(duì)于此鏈表，我們可以利用上文提到的操作方法，執(zhí)行插入、刪除以及查找操作，但對(duì)于ReHash操作則比較困難。

如圖4，在ReHash過(guò)程中，一個(gè)典型的操作是遍歷舊表中的每個(gè)節(jié)點(diǎn)，計(jì)算其在新表中的位置，然后將其移動(dòng)至新表中。期間我們需要操縱3次指針：

1. 將A的next指針指向D
2. 將B的next指針指向C​
3. 將C的next指針指向E

而這三次指針操作必須同時(shí)完成，才能保證移動(dòng)操作的原子性。但我們不難看出，CAS操作每次只能保證一個(gè)變量的值被原子性地驗(yàn)證并更新，無(wú)法滿足同時(shí)驗(yàn)證并更新三個(gè)指針的需求。

于是我們不妨換一個(gè)思路，既然移動(dòng)節(jié)點(diǎn)的操作如此困難，我們可以使所有節(jié)點(diǎn)始終保持有序狀態(tài)，從而避免了移動(dòng)操作。在典型的HashMap實(shí)現(xiàn)中，數(shù)組的長(zhǎng)度始終保持為2ⁱ，而從Hash值映射為數(shù)組下標(biāo)的過(guò)程，只是簡(jiǎn)單地對(duì)數(shù)組長(zhǎng)度執(zhí)行取模運(yùn)算（即僅保留Hash二進(jìn)制的后i位）。當(dāng)ReHash時(shí)，數(shù)組長(zhǎng)度加倍變?yōu)?ⁱ⁺¹，舊數(shù)組第j項(xiàng)鏈表中的每個(gè)節(jié)點(diǎn)，要么移動(dòng)到新數(shù)組中第j項(xiàng)，要么移動(dòng)到新數(shù)組中第j+2ⁱ項(xiàng)，而它們的唯一區(qū)別在于Hash值第i+1位的不同（第i+1位為0則仍為第j項(xiàng)，否則為第j+2ⁱ項(xiàng)）。

如圖5，我們將所有節(jié)點(diǎn)按照Hash值的翻轉(zhuǎn)位序（如1101->1011）由小到大排列。當(dāng)數(shù)組大小為8時(shí)，2、18在一個(gè)組內(nèi)；3、 11、27在另一個(gè)組內(nèi)。每組的開(kāi)始，插入一個(gè)哨兵節(jié)點(diǎn)，以方便后續(xù)操作。為了使哨兵節(jié)點(diǎn)正確排在組的最前方，我們將正常節(jié)點(diǎn)Hash的***位（翻轉(zhuǎn)后變?yōu)?**位）置為1，而哨兵節(jié)點(diǎn)不設(shè)置這一位。

當(dāng)數(shù)組擴(kuò)容至16時(shí)（見(jiàn)圖6），第二組分裂為一個(gè)只含3的組和一個(gè)含有11、27的組，但節(jié)點(diǎn)之間的相對(duì)順序并未改變。這樣在ReHash時(shí)，我們就不需要移動(dòng)節(jié)點(diǎn)了。

實(shí)現(xiàn)細(xì)節(jié)

由于擴(kuò)容時(shí)數(shù)組的復(fù)制會(huì)占用大量的時(shí)間，這里我們采用了將整個(gè)數(shù)組分塊，懶惰建立的方法。這樣，當(dāng)訪問(wèn)到某下標(biāo)時(shí)，僅需判斷此下標(biāo)所在塊是否已建立完畢（如果沒(méi)有則建立）。

另外定義size為當(dāng)前已使用的下標(biāo)范圍，其初始值為2，數(shù)組擴(kuò)容時(shí)僅需將size加倍即可；定義count代表目前HashMap中包含的總節(jié)點(diǎn)個(gè)數(shù)（不算哨兵節(jié)點(diǎn)）。

初始時(shí)，數(shù)組中除第0項(xiàng)外，所有項(xiàng)都為null。第0項(xiàng)指向一個(gè)僅有一個(gè)哨兵節(jié)點(diǎn)的鏈表，代表整條鏈的起點(diǎn)。初始時(shí)全貌見(jiàn)圖7，其中淺綠色代表當(dāng)前未使用的下標(biāo)范圍，虛線箭頭代表邏輯上存在，但實(shí)際未建立的塊。

初始化下標(biāo)操作

數(shù)組中為null的項(xiàng)都認(rèn)為處于未初始化狀態(tài)，初始化某個(gè)下標(biāo)即代表建立其對(duì)應(yīng)的哨兵節(jié)點(diǎn)。初始化是遞歸進(jìn)行的，即若其父下標(biāo)未初始化，則先初始化其父下標(biāo)。（一個(gè)下標(biāo)的父下標(biāo)是其移除***二進(jìn)制位后得到的下標(biāo)）大致代碼如下：

privatevoidinitializeBucket(intbucketIdx) { 
 
    intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx); 
 
    if(getBucket(parentIdx) ==null) 
 
        initializeBucket(parentIdx); 
 
    Node dummy =newNode(); 
 
    dummy.hash = Integer.reverse(bucketIdx); 
 
    dummy.next =newAtomicReference<>(); 
 
    setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy)); 
 
 
} 

其中g(shù)etBucket即封裝過(guò)的獲取數(shù)組某下標(biāo)內(nèi)容的方法，setBucket同理。listInsert將從指定位置開(kāi)始查找適合插入的位置插入給定的節(jié)點(diǎn)，若鏈表中已存在hash相同的節(jié)點(diǎn)則返回那個(gè)已存在的節(jié)點(diǎn)；否則返回新插入的節(jié)點(diǎn)。

插入操作

• 首先用HashMap的size對(duì)鍵的hashCode取模，得到應(yīng)插入的數(shù)組下標(biāo)。
• 然后判斷該下標(biāo)處是否為null，如果為null則初始化此下標(biāo)。
• 構(gòu)造一個(gè)新的節(jié)點(diǎn)，并插入到適當(dāng)位置，注意節(jié)點(diǎn)中的hash值應(yīng)為原h(huán)ashCode經(jīng)過(guò)位翻轉(zhuǎn)并將***位置1之后的值。
• 將節(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)器加1，若加1后節(jié)點(diǎn)過(guò)多，則僅需將size改為size*2，代表對(duì)數(shù)組擴(kuò)容（ReHash）。

查找操作 

• 找出待查找節(jié)點(diǎn)在數(shù)組中的下標(biāo)。
• 判斷該下標(biāo)處是否為null，如果為null則返回查找失敗。
• 從相應(yīng)位置進(jìn)入鏈表，順次尋找，直至找出待查找節(jié)點(diǎn)或超出本組節(jié)點(diǎn)范圍。

刪除操作

• 找出應(yīng)刪除節(jié)點(diǎn)在數(shù)組中的下標(biāo)。
• 判斷該下標(biāo)處是否為null，如果為null則初始化此下標(biāo)。
• 找到待刪除節(jié)點(diǎn)，并從鏈表中刪除。（注意由于哨兵節(jié)點(diǎn)的存在，任何正常元素只被其唯一的前驅(qū)節(jié)點(diǎn)所引用，不存在被前驅(qū)節(jié)點(diǎn)與數(shù)組中指針同時(shí)引用的情況，從而不會(huì)出現(xiàn)需要同時(shí)修改多個(gè)指針的情況）
• 將節(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)器減1。

原文鏈接：http://coolshell.cn/articles/9703.html