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 カウンタ =newAtomicInteger(3);
publicvoidaddCounter() {
のために（;;） {
intoldValue = counter.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
戻る;
}
}
このうち、compareAndSet メソッドは、counter の既存の値が oldValue であるかどうかを確認し、そうであれば、操作は成功し、true が返されます。それ以外の場合、操作は失敗し、false が返されます。
カウンタの新しい値を計算するときに、他のスレッドがカウンタの値を変更すると、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(ノードヘッド、ノードc) {
のために（;;） {
ノード a = findInsertionPlace(head)、b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
戻る;
}
}
(Node クラスの次のフィールドは AtomicReference<Node> 型で、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 に示すように、ハッシュ値の逆順 (1101->1011 など) に従って、すべてのノードを昇順に配置します。配列サイズが 8 の場合、2 と 18 は 1 つのグループに属し、3、11 と 27 は別のグループに属します。各グループの先頭に、後続の操作を容易にするためにセンチネル ノードが挿入されます。センチネル ノードをグループの先頭に正しく配置するために、通常のノード ハッシュの最上位ビット (反転後は最下位ビットになります) を 1 に設定しますが、センチネル ノードはこのビットを設定しません。
配列が 16 に拡張されると (図 6 を参照)、2 番目のグループは 3 のみを含むグループと 11 と 27 を含むグループに分割されますが、ノード間の相対的な順序は変わりません。この方法では、ReHash 中にノードを移動する必要がありません。
実装の詳細
展開時に配列のコピーに時間がかかるので、ここでは配列全体をブロックに分割してlazyに作成する方法を採用します。このように、ある添え字にアクセスしたときは、その添え字が存在するブロックが確立されているかどうかを判断するだけで済みます（確立されていない場合は作成します）。
さらに、サイズは現在使用されている添え字の範囲として定義され、その初期値は 2 です。配列が展開されるときは、サイズを 2 倍にするだけで済みます。count は、現在 HashMap に含まれているノードの総数を表すために定義されます (センチネルノードはカウントしません)。
最初は、配列内の 0 番目の項目を除くすべての項目は null です。項目 0 は、チェーン全体の開始点を表すセンチネル ノードが 1 つだけあるリンク リストを指します。最初の全体像を図 7 に示します。薄緑色は現在使用されていない添字範囲を表し、点線の矢印は論理的に存在するが実際には確立されていないブロックを表します。
添字演算の初期化
配列内の null 項目は、初期化されていない状態であると見なされます。特定の添え字を初期化することは、対応するセンチネル ノードを確立することを意味します。初期化は再帰的に実行されます。つまり、親の添字が初期化されていない場合は、親の添字が最初に初期化されます。 (添字の親添字は、バイナリの最上位ビットを削除して得られる添字です。) おおよそのコードは次のとおりです。
次のようにコードをコピーします。
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = BucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==null)
初期化バケット(親Idx);
ノードダミー =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
このうち getBucket は配列内の特定の添字の内容を取得するためのカプセル化されたメソッドであり、setBucket も同様です。 listInsert は、指定された位置から開始する適切な位置に指定されたノードを挿入します。同じハッシュを持つノードがリンク リストにすでに存在する場合は、既存のノードを返します。それ以外の場合は、新しく挿入されたノードを返します。
挿入操作
まず、HashMap のサイズを使用してキーの hashCode を法化し、挿入する必要がある配列添字を取得します。
次に、添え字が null かどうかを判断し、null の場合は添え字を初期化します。
新しいノードを構築し、それを適切な位置に挿入します。ノード内のハッシュ値は、ビット反転して最小位置を 1 に設定した後の元の hashCode の値である必要があることに注意してください。
ノード数カウンタに 1 を追加します。1 を追加した後、ノードが多すぎる場合は、サイズを size*2 に変更するだけで済みます。これは、配列の拡張 (ReHash) を意味します。
検索操作
配列内で検索するノードのインデックスを見つけます。
添字が null かどうかを確認します。null の場合は、検索失敗が返されます。
対応する位置からリンク リストを入力し、検索するノードが見つかるか、このノード グループの範囲を超えるまで順次検索します。
削除操作
配列内で削除する必要があるノードのインデックスを見つけます。
添字が null かどうかを判断し、null の場合は添字を初期化します。
削除するノードを見つけてリンク リストから削除します。 (センチネル ノードの存在により、通常の要素はその唯一の先行ノードによってのみ参照されることに注意してください。先行ノードと配列内のポインタによって同時に参照される状況は存在しません。複数のポインターを同時に変更する必要はありません。)
ノード番号カウンタを 1 減らします。