java無鎖hashmap原理與實作詳解

java多線程環境中應用HashMap，主要有以下幾種選擇：使用線程安全的java.util.Hashtable作為替代使用java.util.Collections.synchronizedMap方法，將現有的HashMap物件包裝為線程安全的。使用java.util.concurrent.ConcurrentHashMap類別作為替代，它具有非常好的效能。
而以上幾種方法在實現的具體細節上，都或多或少地用到了互斥鎖。互斥鎖會造成執行緒阻塞，降低運作效率，並有可能產生死鎖、優先權翻轉等一系列問題。

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

Java中的原子操作

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

例如我們希望實作一個全域公用的計數器，那麼可以：

privateAtomicInteger counter =newAtomicInteger(3); 

publicvoidaddCounter() { 

    for(;;) { 

        intoldValue = counter.get(); 

        intnewValue = oldValue +1; 

        if(counter.compareAndSet(oldValue, newValue)) 

            return; 

    } 

}

其中，compareAndSet方法會檢查counter現有的值是否為oldValue，如果是，則將其設為新值newValue，操作成功並傳回true ；否則操作失敗並回傳false。

當計算counter新值時，若其他執行緒將counter的值改變，compareAndSwap就會失敗。此時我們只需在外面增加一層循環，不斷嘗試這個過程，那麼最終一定會成功將counter值+1。 （其實AtomicInteger已經為常用的+1/-1操作定義了incrementAndGet與decrementAndGet方法，以後我們只需簡單調用它即可）

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

無鎖鍊錶的實作
在實作無鎖HashMap之前，讓我們先來看看比較簡單的無鎖鍊錶的實作方法。

以插入操作為例：

首先我們需要找到待插入位置前面的節點A和後面的節點B。
接著新建一個節點C，並使其next指標指向節點B。 （見圖1）
最後使節點A的next指標指向節點C。 （見圖2）

但在操作中途，有可能其他執行緒在A與B直接也插入了一些節點（假設為D），如果我們不做任何判斷，可能造成其他執行緒插入節點的遺失。 （見圖3）我們可以利用CAS操作，在為節點A的next指標賦值時，判斷其是否仍指向B，如果節點A的next指標發生了變化則重試整個插入操作。大致程式碼如下：

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型別的原子性參考)

無鎖鍊錶的查找操作與普通鍊錶沒有差別。而其刪除操作，則需要找到待刪除節點前方的節點A和後方的節點B，利用CAS操作驗證並更新節點A的next指針，使其指向節點B。

無鎖HashMap的困難與突破
HashMap主要有插入、刪除、查找、ReHash四種基本操作。一個典型的HashMap實現，會用到一個數組，數組的每個元素為一個節點的鍊錶。對於此鍊錶，我們可以利用上文提到的操作方法，執行插入、刪除以及查找操作，但對於ReHash操作則比較困難。

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

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

於是我們不妨換一個思路，既然移動節點的操作如此困難，我們可以使所有節點始終保持有序狀態，從而避免了移動操作。在典型的HashMap實作中，數組的長度始終保持為2i，而從Hash值映射為數組下標的過程，只是簡單地對數組長度執行取模運算（即僅保留Hash二進制的後i位元）。當ReHash時，數組長度加倍變為2i+1，舊數組第j項鍊表中的每個節點，要么移動到新數組中第j項，要么移動到新數組中第j+2i項，而它們的唯一差異在於Hash值第i+1位的不同（第i+1位為0則仍為第j項，否則為第j+2i項）。

如图5，我们将所有节点按照Hash值的翻转位序（如1101->1011）由小到大排列。当数组大小为8时，2、18在一个组内；3、 11、27在另一个组内。每组的开始，插入一个哨兵节点，以方便后续操作。为了使哨兵节点正确排在组的最前方，我们将正常节点Hash的最高位（翻转后变为最低位）置为1，而哨兵节点不设置这一位。

当数组扩容至16时（见图6），第二组分裂为一个只含3的组和一个含有11、27的组，但节点之间的相对顺序并未改变。这样在ReHash时，我们就不需要移动节点了。

实现细节

由于扩容时数组的复制会占用大量的时间，这里我们采用了将整个数组分块，懒惰建立的方法。这样，当访问到某下标时，仅需判断此下标所在块是否已建立完毕（如果没有则建立）。

另外定义size为当前已使用的下标范围，其初始值为2，数组扩容时仅需将size加倍即可；定义count代表目前HashMap中包含的总节点个数（不算哨兵节点）。

初始时，数组中除第0项外，所有项都为null。第0项指向一个仅有一个哨兵节点的链表，代表整条链的起点。初始时全貌见图7，其中浅绿色代表当前未使用的下标范围，虚线箭头代表逻辑上存在，但实际未建立的块。

初始化下标操作

数组中为null的项都认为处于未初始化状态，初始化某个下标即代表建立其对应的哨兵节点。初始化是递归进行的，即若其父下标未初始化，则先初始化其父下标。（一个下标的父下标是其移除最高二进制位后得到的下标）大致代码如下：

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)); 

 
}

其中getBucket即封装过的获取数组某下标内容的方法，setBucket同理。listInsert将从指定位置开始查找适合插入的位置插入给定的节点，若链表中已存在hash相同的节点则返回那个已存在的节点；否则返回新插入的节点。

插入操作

首先用HashMap的size对键的hashCode取模，得到应插入的数组下标。
然后判断该下标处是否为null，如果为null则初始化此下标。
构造一个新的节点，并插入到适当位置，注意节点中的hash值应为原hashCode经过位翻转并将最低位置1之后的值。
将节点个数计数器加1，若加1后节点过多，则仅需将size改为size*2，代表对数组扩容（ReHash）。

查找操作

找出待查找节点在数组中的下标。
判断该下标处是否为null，如果为null则返回查找失败。
从相应位置进入链表，顺次寻找，直至找出待查找节点或超出本组节点范围。

删除操作

找出应删除节点在数组中的下标。
判断该下标处是否为null，如果为null则初始化此下标。
找到待删除节点，并从链表中删除。（注意由于哨兵节点的存在，任何正常元素只被其唯一的前驱节点所引用，不存在被前驱节点与数组中指针同时引用的情况，从而不会出现需要同时修改多个指针的情况）
将节点个数计数器减1。

更多java無鎖hashmap原理與實作詳解相关文章请关注PHP中文网！