java多線程環(huán)境中應(yīng)用HashMap，主要有以下幾種選擇：使用線程安全的java.util.Hashtable作為替代?使用java.util.Collections.synchronizedMap方法，將已有的HashMap對象包裝為線程安全的。使用java.util.concurrent.ConcurrentHashMap類作為替代，它具有非常好的性能。
而以上幾種方法在實現(xiàn)的具體細節(jié)上，都或多或少地用到了互斥鎖?；コ怄i會造成線程阻塞，降低運行效率，并有可能產(chǎn)生死鎖、優(yōu)先級翻轉(zhuǎn)等一系列問題。

CAS(Compare And Swap)是一種底層硬件提供的功能，它可以將判斷并更改一個值的操作原子化。

Java中的原子操作

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

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

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

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

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

無鎖鏈表的實現(xiàn)
在實現(xiàn)無鎖HashMap之前，讓我們先來看一下比較簡單的無鎖鏈表的實現(xiàn)方法。

以操作為例：

首先我們需要找到待位置前面的節(jié)點A和后面的節(jié)點B。
然后新建一個節(jié)點C，并使其next指針指向節(jié)點B。（見圖1）
最后使節(jié)點A的next指針指向節(jié)點C。（見圖2）

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

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

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

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

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

將A的next指針指向D
將B的next指針指向C?
將C的next指針指向E
而這三次指針操作必須同時完成，才能保證移動操作的原子性。但我們不難看出，CAS操作每次只能保證一個變量的值被原子性地驗證并更新，無法滿足同時驗證并更新三個指針的需求。

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

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

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

實現(xiàn)細節(jié)

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

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

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

初始化下標操作

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

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

操作

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

查找操作

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

刪除操作

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

最新評論