Javaロックフリーハッシュマップの原理と実装の詳細な説明

Java マルチスレッド環境で HashMap を適用する場合、主に次のオプションがあります: 代替としてスレッドセーフな java.util.Hashtable を使用し、既存の HashMap オブジェクトをラップするために java.util.Collections.synchronizedMap メソッドを使用します。スレッドセーフ。代わりに、パフォーマンスが非常に優れている 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 メソッドは、カウンターの既存の値が oldValue であるかどうかを確認し、そうである場合は、新しい値に設定されます。 newValue。操作は成功し、 true を返します。それ以外の場合、操作は失敗し、 false を返します。

counter の新しい値を計算するときに、他のスレッドが counter の値を変更すると、compareAndSwap は失敗します。この時点で必要なのは、外部にループのレイヤーを追加し、このプロセスを試行し続けることだけです。そうすれば、最終的にカウンター値を 1 ずつ増やすことができます。 (実際、AtomicInteger は、一般的に使用される +1/-1 操作用に、incrementAndGet メソッドと decrementAndGet メソッドをすでに定義しています。今後は、単に呼び出すだけで済みます。)

AtomicInteger に加えて、java.util.concurrent.atomic パッケージもは、AtomicReference タイプと AtomicReferenceArray タイプを提供します。これらは、それぞれアトミック参照とアトミック参照配列 (参照の配列) を表します。

ロックフリーリンクリストの実装
ロックフリーHashMapを実装する前に、まず比較的簡単なロックフリーリンクリストの実装方法を見てみましょう。

挿入操作を例に挙げます:

まず、挿入される位置の前にあるノード A とその後ろにあるノード B を見つける必要があります。
次に、新しいノード C を作成し、その次のポインターがノード B を指すようにします。 (図 1 を参照)
最後に、ノード A の次のポインターがノード C を指すようにします。 (図 2 を参照)

しかし、操作中に、他のスレッドが A と B (D とする) に直接いくつかのノードを挿入した可能性があります。何も判断しないと、他のスレッドによって挿入されたノード。 (図 3 を参照) CAS 操作を使用すると、値を割り当てるときにノード A の次のポインターがまだ B を指しているかどうかを判断できます。ノード A の次のポインターが変更された場合は、挿入操作全体を再試行します。おおよそのコードは次のとおりです:

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 クラスの次のフィールドは AtomicReference 型で、Node 型を指すアトミック参照です)

ロックフリーのリンク リストの検索操作は次のとおりです。通常のリンクリストと何ら変わりません。削除操作では、削除するノードの前にあるノード A とその後ろにあるノード B を見つけ、CAS 操作を使用してノード A の次のポインターを検証し、ノード B を指すように更新する必要があります。

ロックフリーHashMapの困難さと突破口
HashMapには主に、挿入、削除、検索、再ハッシュという4つの基本操作があります。一般的な HashMap 実装では配列が使用され、配列の各要素はノードのリンクされたリストです。このリンクされたリストの場合、上記の操作方法を使用して挿入、削除、検索操作を実行できますが、ReHash 操作はさらに困難です。

図 4 に示すように、ReHash プロセス中の一般的な操作は、古いテーブル内の各ノードを走査し、新しいテーブル内での位置を計算し、それを新しいテーブルに移動することです。この期間中に、ポインタを 3 回操作する必要があります:

A の次のポインタを D にポイントする
B の次のポインタを C にポイントする
C の次のポインタを E にポイントする
これら 3 つのポインタ操作は、次の時点で完了する必要があります。同時に、移動操作のアトミック性を確保します。しかし、CAS 操作では一度に 1 つの変数の値がアトミックに検証および更新されることしか保証できず、3 つのポインターを同時に検証および更新するニーズを満たすことができないことを理解するのは難しくありません。

そこで、ノードを移動する操作は非常に難しいため、すべてのノードを常に順序付けられた状態に保ち、移動操作を回避することができます。典型的な HashMap 実装では、配列の長さは常に 2i のままで、ハッシュ値を配列の添え字にマッピングするプロセスは、単に配列の長さに対してモジュロ演算を実行するだけです (つまり、ハッシュ バイナリの最後の i ビットのみが保持されます）。 ReHash すると、配列の長さは 2 倍の 2i+1 になり、古い配列の j 番目のネックレス リストの各ノードは、新しい配列の j 番目の項目に移動されるか、j+2i 番目の項目に移動されます。新しい配列の項目とその唯一の違いは、ハッシュ値の 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ロックフリーハッシュマップの原理と実装の詳細な説明相关文章请关注PHP中文网！