ハッシュテーブルは非常に効率的なデータ構造であり、ハッシュ関数の優れた設計により、追加、削除、変更、および検索操作がO（1）レベルに達することができることがわかっています。 Javaは、既製のハッシュ構造、つまりハッシュマップクラスを提供します。前の記事では、HashMapクラスを紹介し、そのすべての方法が同期されていないことを知っていたため、マルチスレッド環境では安全ではありません。この目的のために、Javaは別のハッシュテーブルクラスを提供します。これは、マルチスレッド同期の処理において非常にシンプルで粗い、つまり、ハッシュマップに基づいた同期キーワードを使用してすべてのメソッドをロックします。この方法は単純ですが、問題につながります。つまり、ハッシュテーブルを同時に操作できるスレッドは1つだけです。これらのスレッドが読み取り操作のみであっても、それらはキューに巻き込まれなければなりません。これは、非常に競争力のあるマルチスレッド環境でのパフォーマンスに大きく影響します。この記事で導入された同時ハッシュマップは、この問題を解決することです。セグメント化されたロックを使用してロックを細かく微調整するため、複数のスレッドがハッシュテーブルを同時に操作できるようになり、パフォーマンスが大幅に向上します。次の図は、その内部構造の概略図です。
1. CONCURRENTHASHMAPにはどのようなメンバー変数がありますか？
// default初期化容量容量静的最終int default_initial_capacity = 16; // default load factic final final final final final final final final final final final default_load_factor = 0.75f; // default scurrency static final int default_concurrency_level = 16; //セット最大容量static static final int maximince_capacity = 1 << 30;セグメントロックの静的最終int max_segments = 1 << 16; //レトリ数静的final int retries_before_lock = 2; //セグメントロックのマスク値最終intセグメントマスク; //セグメントロックアレイ最終セグメント<k、v> [] segments;
この記事を読む前に、読者はこれらのメンバー変数の特定の意味と機能を理解できないと信じていますが、読者は辛抱強く読むことをお勧めします。これらのメンバー変数の役割は、特定のシナリオで1つずつ導入されます。ここでは、読者はこれらのメンバー変数をよく見なければならないだけです。ただし、今すぐ知る必要があるいくつかの変数がまだあります。たとえば、セグメントアレイはセグメントロックのセットを表し、並行性レベルはセグメントロックの数（同時に動作するスレッドの数も意味します）を表し、初期化容量はコンテナ全体の容量を表し、荷重係数はコンテナ要素がどれだけ到達できるかを表します。
2。セグメントロックの内部構造は何ですか？
// segment lock static final classセグメント<k、v> reintrantlock実装{//最大スピン番号Static final int max_scan_retries = runtime.getRuntime（）。利用可能なProcessors（）> 1？ 64：1; // hastテーブル一時的な揮発性ハシェントリー<k、v> []テーブル; //一時的な要素の総数一時的なカウント。 //変更の数Transient Int ModCount; //要素しきい値過渡的intしきい値。 //ロードファクターファイナルフロートロードファクター。 //次のコンテンツを省略します...}セグメントは、CONCURRENTHASHMAPの静的な内部クラスであり、ReentrantLockから継承することがわかります。そのため、本質的にロックです。内部的にハッシュアレイ（ハッシュテーブル）を保持し、配列を追加、削除、変更、検索するすべての方法がスレッドセーフであることを保証します。特定の実装については後で説明します。同時ハッシュマップの追加、削除、変更、チェックに関するすべての操作をセグメントに委ねることができるため、concurrenthashmapはマルチスレッド環境で安全であることを保証できます。また、異なるセグメントは異なるロックであるため、マルチスレッドは同時に異なるセグメントを動作させることができます。つまり、マルチスレッドは同時に同時に動作することができます。これにより、ハッシュテーブルの欠陥を回避し、パフォーマンスを大幅に改善できます。
3. CONCURRENTHASHMAPは何を初期化しましたか？
// core constructor @suppresswarnings（ "un -checked"）public concurrenthashmap（int initialcapacity、float loadfactor、int concrurencylevel）{if（！（loadfactor> 0）|| icrurcurencylevel <= 0）{show new legalargumentexception（）; } //並行性レベルが制限より大きくないことを確認してください（concurrencylevel> max_segments）{concurrencylevel = max_segments; } int sshift = 0; int ssize = 1; // ssizeが2のパワーであり、並行性レベル以上の最も近い数であることを確認してください（ssize <concurrencyLevel）{++ sshift; ssize << = 1; } //セグメントのシフト値を計算しますthis.segmentshift = 32 -sshift; //セグメントロックのマスク値を計算します。 //総初期容量は、InitialCapacity> Maximum_Capacity）{initialCapacity = Maximix_Capacity; } //各セグメントロックの初期容量を取得しますint c = initialcapacity /ssize; //セグメント化されたロック容量の合計は、（c * ssize <initialcapacity）{++ c; } int cap = min_segment_table_capacity; // CAPが2のパワーであり、C以下の最も近い数値であることを確認してください（CAP <C）{cap << = 1; } //新しいセグメントオブジェクトテンプレートセグメント<k、v> s0 =新しいセグメント<k、v>（loadfactor、（int）（cap * loadfactor）、（hashentry <k、v> []）new Hashentry [cap]）; //指定されたサイズセグメントの新しいセグメントロック配列を作成<K、v> [] ss =（segment <k、v> []）new segment [ssize]; // Unsafeを使用して、配列の0番目の要素を割り当てません。 this.segments = ss;}concurrenthashmapには複数のコンストラクターがありますが、上に投稿されているのはそのコアコンストラクターであり、他のコンストラクターはそれを呼び出して初期化を完了します。コアコンストラクターは、3つのパラメーター、つまり初期容量、荷重係数、並行性レベルを渡す必要があります。メンバー変数を早期に導入すると、デフォルトの初期容量が16、負荷係数が0.75F、同時実行レベルは16であることがわかります。これで、コアコンストラクターのコードが表示されました。最初に、着信する同時レベルを介してssizeを計算します。 Ssizeはセグメントアレイの長さです。このように、アレイにロックされたセグメントの添え字をハッシュ＆ssize-1で計算できます。入ってくる並行性レベルは2のパワーであることを保証することはできないため、セグメントアレイの長さとして直接使用することはできません。したがって、同時性レベルに最も近い2の電力を見つけて、それを配列の長さとして使用する必要があります。 CONCURRENCYLEVEL = 15が現在渡された場合、上記のコードはSSIZE = 16およびSSHIFT = 4を計算できます。次に、SegmentShift = 16およびSegmentMask = 15をすぐに計算できます。ここのセグメントシフトはセグメントロックのシフト値であり、セグメントマスクはセグメントロックのマスク値であることに注意してください。これらの2つの値は、配列内のセグメントロックの添え字を計算するために使用されます。これについては、以下で説明します。セグメントロックの数を計算した後、各セグメントロックの容量は、総着信容量とその値c = initial -capacity/ssizeに基づいて計算できます。セグメントロックの容量は、ハッシュアレイの長さであり、2のパワーであることも保証する必要があります。上記のCの値はこれを保証できないため、Cはハッシュヘントアレイの長さとして直接使用できません。 Cに最も近い2の別のパワーを見つけ、この値をキャップに割り当ててから、ハッシュエントリーアレイの長さとしてキャップを使用する必要があります。 SsizeとCapができたので、新しいセグメントロックアレイセグメント[]と要素アレイHashentry []を作成できます。 JDK1.6とは異なり、JDK1.7にセグメントアレイのみが作成され、初期化されていないことに注意してください。セグメントの初期化の動作は、挿入操作に任されました。
4.ロックを見つけて要素を見つける方法は？
//ハッシュコードに基づいてセグメントロックを取得@SuppressWarnings（ "Un -checked"）プライベートセグメント<K、v> segmentforhash（int h）{long u =（（（h >>> segmentshift）＆segmentmask）<< sshift） + sbase; return（segment <k、v>）unsafe.getobjectvolatile（segments、u）;} //ハッシュコード@suppresswarnings（ "un -checked"）static final <k、v> hashentry <k、v> entryforhash（segment <k、v> se）{int h）{hashentry <k、v> return（seg == null ||（tab = seg.table）== null）？ null ：（ hashentry <k、v>）unsafe.getObjectVolatile（（long）（（long）（（long）＆h））<< tshift） + tbase）;} JDK1.7では、Unsafeが配列要素を取得するために使用されるため、JDK1.6よりもアレイ要素オフセットを計算するためのいくつかのコードを次に示します。当面はこれらのコードに注意を払いません。これで、次の2つのポイントを知る必要があります。
a。ハッシュコードを介して配列にロックされたセグメントの添え字を計算します：（h >>> segmentshift）＆segmentmask。
b。ハッシュコードで配列内の要素の添え字を計算します：（tab.length -1）＆h。
次に、コンストラクターに渡された2つのパラメーターがinitialcapacity = 128、concrurencyLevel = 16であると仮定します。計算によれば、Ssize = 16、Sshift = 4、segmentshift = 28、segmentmask = 15を取得できます。同様に、各セグメントロックのハッシュアレイの長さは8と計算されるため、length-1 = 7。これらの値に基づいて、下の図を介して同じハッシュコードに基づいてセグメントロックと要素を見つける方法を説明します。
セグメントロックと要素の位置は、要素のハッシュコードによって決定されることがわかります。位置決めセグメントロックは、ハッシュコードの高い値（32ビットから始まる）であり、位置決め要素はハッシュコードの値が低いです。今、質問があります。それらは、32ビットの左端から32ビットの右端から始まります。ある時点で対立はありますか？ Maximum_capacity = 1 << 30、max_segments = 1 << 16メンバー変数で見つけることができます。つまり、ポジショニングセグメントロックとポジショニング要素に使用されるビットの総数は30を超えず、ポジショニングセグメントロックに使用されるビット数は16を超えないため、少なくとも2ビットが残ります。
5.要素を具体的に見つける方法は？
// ValuePublic v Get（Object Key）{segment <k、v> s; Hashentry <K、v> []タブ; //ハッシュ関数int h = hash（key）を使用してハッシュコードを計算します。 //ハッシュコードに基づいてセグメントロックのインデックスを計算しますu =（（（h >>> segmentshift）＆segmentmask）<< sshift） + sbase; //セグメントロックと対応するハッシュテーブルを取得します（（s =（segment <k、v>）unsafe.getobjectvolatile（segments、u））！= null &&（tab = s.table）！= null）{//ハッシュコードに従ってリンクリストのリンクリストのヘッダーノードを取得します。 （hashentry <k、v>）unsafe.getobjectvolatile（（long）（（long））<< tshift） + tbase）; //キーとハッシュに従って対応する要素の値に従い、（k = e.key）== key ||（e.hash == h && key.equals（k）））{return e.value; }}} nullを返します;}JDK1.6では、セグメントロックのGETメソッドはサブスクリプトを介して配列要素にアクセスしますが、JDK1.7では、配列の要素はUnsafeのGetobjectolatileメソッドを介して読み取られます。なぜこれをするのですか？セグメントオブジェクトによって保持されているハッシュエントリーアレイ参照は揮発性であるが、配列内の要素参照は揮発性ではないため、アレイ要素へのマルチスレッドの変更は安全ではなく、アレイでまだ構築されていないオブジェクトを読み取る可能性があることを知っています。 JDK1.6では、2番目のロック読み取りが安全であることが保証されており、JDK1.7では、UnsafeのGetobjectvolatileメソッドもこれを保証することです。 GetObjectVolatileメソッドを使用した配列要素の読み取りには、最初に配列内の要素のオフセットを取得する必要があります。ここでは、ハッシュコードによれば、配列のセグメントロックのオフセットはuであり、その後、オフセットuはセグメントロックを読み取ろうとするために使用されます。セグメントロックアレイは建設中に初期化されないため、ヌル値を読み取ることができるため、最初に判断が必要です。セグメントロックとその内部ハッシュテーブルが空でないことを確認した後、ハッシュアレイの要素はハッシュコードを介して読み取られます。上の構造図によると、この時点でリンクリストのヘッダーノードが取得されていることがわかります。次に、リンクされたリストを最初から最後までトラバースして検索します。対応する値が見つかった場合、返されます。そうしないと、nullが返されます。上記は、要素を見つけるプロセス全体です。
6.挿入要素を実装する方法は？
// key-valueペアをセットに追加します（ある場合は置き換えます）@suppresswarnings（ "unchecked"）public v put（k key、v value）{segment <k、v> s; //渡された値は空にすることはできません（値== null）新しいnullpointerexception（）; //ハッシュ関数int hash = hash（key）を使用してハッシュコードを計算します。 //ハッシュコードint j =（hash >>> segmentshift）＆segmentmaskに基づいて、セグメントロックの添え字を計算します。 //添え字に基づいてセグメントロックを取得しようとします。 } //セグメントロックリターンS.put（key、hash、value、false）;} // key-valueペアをセットに追加する（存在しない場合は追加）@suppresswarnings（ "un-checked"）public v pustifabsent（k key、v value）{segment <k、v> s; //渡された値は空にすることはできません（値== null）新しいnullpointerexception（）; //ハッシュ= hash（key）でハッシュコードを計算します。 //ハッシュコードint j =（hash >>> segmentshift）＆segmentmaskに基づいて、セグメントロックの添え字を計算します。 //添え字に基づいてセグメントロックを取得してみてください。 } //カレンダーセグメントロックのプット方法はs.put（key、hash、value、true）;}CONCURRENTHASHMAPには、キー値のペアを追加する2つの方法があります。存在する場合、PUTメソッドを介して追加すると上書きされます。 put fabsentメソッドを介してfabsentメソッドが追加され、上書きはありません。どちらの方法でも、操作を完了するためにセグメントロックのプット方法を呼び出しますが、渡された最後のパラメーターは異なります。上記のコードでは、最初に、キーのハッシュコードに基づいて配列のセグメントロックのサブスクリプトを計算し、その後、安全でないクラスのgetobjectメソッドを使用して、添え字に従ってセグメントロックを読み取ります。 CONCURRENTHASHMAPを構築するときにセグメントアレイの要素は初期化されないため、null値を読み取り、新しいセグメントロックをEnsuresement Methodによって作成できます。セグメントロックを取得した後、PUTメソッドを呼び出して追加操作を完了します。操作方法を見てみましょう。
//キー値ペアの追加v Put（k key、int hash、v value、booleanの唯一の範囲）{//ロックを取得してみてください。 null：scanandlockforput（key、hash、value）; v oldvalue; try {hashentry <k、v> [] tab = table; //要素のsubscript int index =（tab.length -1）＆hashを計算します。 //サブスクリプトのハッシュエントリー<k、v> first = entryat（tab、index）に基づいて、リンクリストのヘッダーノードを取得します。 for（hashentry <k、v> e = first ;;）{//リンクリストを送信して要素を見つけ、if（e！= null）{k k; if（（k = e.key）== key ||（e.hash == hash && key.equals（k）））{oldvalue = e.value; //パラメーターに基づいて古い値を置き換えるかどうかを決定します。 ++ modcount; } 壊す; } e = e.next; //見つかっていない場合は、リンクリストにノードを追加} else {//リンクリストのヘッダーにノードノードを挿入if（node！= null）{node.setnext（first）; } else {node = new Hashentry <k、v>（hash、key、value、first）; } //ノードを挿入した後、常に1つのint c = count + 1を追加します。 //要素がしきい値を超えた場合、容量を拡張する場合（c>しきい値&& tab.length <maximix_capacity）{rehash（node）; //それ以外の場合は、HASHテーブルを指定したサブスクリプトをノードnodeに置き換えます} else {setentryat（tab、index、node）; } ++ modcount; count = c; oldvalue = null;壊す; }}}最後に{lock（）; } return oldvalue;}スレッドの安全性を確保するには、セグメント化されたロックに操作をロックする必要があるため、スレッドは最初にロックを取得し、取得が成功した場合は実行を続けます。取得が失敗した場合は、ScanAndLockForputメソッドを呼び出してスピンします。スピンプロセス中に、ハッシュテーブルをスキャンして指定されたキーを見つけます。キーが存在しない場合、新しいハッシュエントリーが作成されるため、ロックを取得した後に再度作成する必要はありません。ロックを待っている間にいくつかのことをするために、それは無駄に時間を無駄にしません。これは著者の善意を示しています。特定のスピン方法については、後で詳しく説明します。さて、最初にフォーカスを引き戻します。スレッドがロックを正常に取得すると、計算されたサブスクリプトに基づいて指定されたサブスクリプトの要素が取得されます。この時点で、リンクリストのヘッダーノードが取得されます。ヘッダーノードが空になっていない場合、リンクされたリストが通過して検索されます。見つけた後、唯一のパラメーターの値に基づいて置換するかどうかを決定します。トラバーサルが見つからない場合、新しいハッシュエントリーはヘッダーノードを指します。この時点で、スピン中にハッシュエントリーが作成された場合、現在のヘッダーノードの隣に直接指します。スピンが作成されていない場合、ここに新しいハッシュエントリーが作成され、ヘッダーノードを指します。リンクリストに要素を追加した後、要素の総数がしきい値を超えるかどうかを確認します。それを超えている場合は、拡張のためにRehashに電話してください。それを超えない場合は、新しく追加されたノードへの配列の対応するサブスクリプト要素を直接参照してください。 Setentryatメソッドは、UnsafeのPutOrderEdObjectメソッドを呼び出すことにより、配列要素の参照を変更します。
7.要素の削除を実装する方法
//指定された要素を削除する（対応する要素を見つけた後に直接削除）public v remove（object key）{//ハッシュ関数を使用してハッシュコードint hash = hash（key）; //ハッシュコードセグメントに基づいてセグメントロックのインデックスを取得<k、v> s = segmentforhash（hash）; //セグメントロックの削除方法をカレンダーreturn s == null？ null：s.remove（key、hash、null）;} //指定された要素を削除（指定値に等しい値を削除）public boolean remove（オブジェクトキー、オブジェクト値）{//ハッシュ関数を使用してハッシュコードint hash = hash（key）;セグメント<k、v> s; //削除メソッド返品値を呼び出す前にセグメントロックが空でないことを確認できます！concurrenthashmapは2つの削除操作を提供します。1つはそれを見つけた後に直接削除することであり、もう1つは最初にそれを比較し、それを見つけた後に削除することです。これらの削除メソッドはどちらも、キーのハッシュコードに基づいて対応するセグメントロックを見つけ、セグメントロックの削除方法を呼び出して削除操作を完了します。セグメントロックの削除方法を見てみましょう。
//指定された要素を削除する最終v remove（Object key、int hash、object value）{//ロックを取得しようとします。 } v oldvalue = null; try {hashentry <k、v> [] tab = table; //要素のsubscript int index =（tab.length -1）＆hashを計算します。 // subscript（link list Headerノード）Hashentry <k、v> e = entryat（tab、index）;に従って配列要素を取得します。 hashentry <k、v> pred = null; //リンクリストを転送して、（e！= null）{k k; //次のノードの後継ノードに次のポイントは、Hashentry <K、V> next = e.next; //キーとハッシュに基づいて対応するノードを検索しますif（（k = e.key）== key ||（e.hash == hash && key.equals（k）））{v v = e.value; // vに等しくない場合に渡された値をスキップし、他の場合に削除します（value == null || value == value.equals（v））{// predが空の場合、削除するノードはヘッダーノードです。 } else {// predノードの継承を次のノードに設定しますpred.setnext（next）; } ++ modcount; - カウント; //要素削除の値を記録oldvalue = v; } 壊す; } // eが探しているノードではない場合は、pred = eへの参照を指します。 //次のノードe = nextを確認します。 }}最後に{Unlock（）; } return oldvalue;}セグメントロックで要素を削除するときは、最初にロックを取得する必要があります。買収が失敗した場合は、スピニングのためにスキャンアンドロック方法を呼び出します。買収が成功した場合は、次のステップを実行します。最初にアレイsubscriptを計算し、次にサブスクリプトを介してハッシュエンテリーアレイの要素を取得します。ここで、リンクリストのヘッダーノードが取得されます。次に、リンクされたリストを横断して検索します。この前に、次のポインターを使用して現在のノードの後継ノードを記録し、キーとハッシュを比較して、それが探しているノードかを確認します。もしそうなら、次の判断を実行します。値が空であるか、値がノードの現在の値に等しい場合、削除のためのIFステートメントが入力され、それ以外の場合は直接スキップされます。 IFステートメントで削除操作を実行する場合、2つの状況があります。現在のノードがヘッダーノードの場合、次のノードをヘッダーノードとして直接設定します。現在のノードがヘッダーノードでない場合は、PREDノードの後継者を次のノードに設定します。ここのプレドノードは、現在のノードの前身を表しています。次のノードをチェックする前に、PREDは現在のノードを指します。これにより、PREDノードが常に現在のノードの前身であることが保証されます。 JDK1.6のJDK1.6とは異なり、Hashentryオブジェクトの次の変数は最終的ではないため、次の値が参照される値を直接変更して要素を削除できることに注意してください。次の変数は揮発性タイプであるため、読み取りスレッドはすぐに最新の値を読み取ることができます。
8。交換要素はどのように具体的に実装されていますか？
//指定された要素を交換します（CAS操作）パブリックブールンの交換（k key、v oldvalue、v newvalue）{//ハッシュ関数を使用してハッシュコードint hash = hash（key）; // oldValueとnewValueが空でないことを確認してください（oldValue == null || newValue == null）新しいnullpointerexception（）; //ハッシュコードセグメントに基づいてセグメントロックのインデックスを取得<k、v> s = segmentforhash（hash）; //セグメントロックの交換メソッドを呼び出すロックはs！= null && s.Replace（key、hash、oldvalue、newvalue）;} //要素操作を置き換えます（cas操作）最終的なブールの置換（kキー、int hash、v newvalue）{//ロックを取得しようとします。 } boolean交換= false; {hashentry <k、v> e; //ハッシュを介してヘッダーノードを直接検索してから、リンクリストをトラバースします（e = entryforhash（this、hash）; e！= null; e = e.next）{k; //キーとハッシュに基づいて交換するノードを検索するif（（k = e.key）== key ||（e.hash == hash && key.equals（k）））{//指定された電流値が正しい場合、（oldvalue.equals（e.value））{e.value = newValue; ++ modcount;交換= true; } //それ以外の場合、操作が実行されない場合は、戻ります。 }}}最後に{lock（）; }交換された返品;}また、Concurrenthashmapは2つの交換操作を提供します。1つは発見後に直接交換することであり、もう1つは最初に比較してから交換（CAS操作）です。これら2つの操作の実装はほぼ同じですが、CAS操作には交換前に比較操作の追加層があることを除いて、操作の1つを簡単に理解する必要があります。ここでは、分析にはCAS操作を使用していますが、これはまだ古いルーチンです。まず、キーのハッシュコードに基づいて対応するセグメントロックを見つけ、次にその置換方法を呼び出します。セグメントロックに交換方法を入力した後、最初にロックを取得する必要があります。買収が失敗した場合は、スピンしてください。買収が成功した場合は、次のステップに進みます。最初に、ハッシュコードに従ってリンクリストのヘッダーノードを取得し、次にキーとハッシュに従ってトラバースと検索します。対応する要素を見つけた後、与えられたoldvalueが現在の値であるかどうかを比較します。そうでない場合は、変更をあきらめ、もしそうなら、それを新しい値に置き換えてください。ハッシュエントリオブジェクトの値フィールドは揮発性があるため、直接交換できます。
9。回転するとき、あなたは正確に何をしましたか？
//ロックを取得するのを待っているスピン（操作を入力）プライベートハッシュエントリー<K、V> scanandLockforput（k key、int hash、v value）{//ハッシュコードHashentry <K、v> first = entryhash（this、hash）に従ってヘッダーノードを取得します。 Hashentry <k、v> e = first; Hashentry <k、v> node = null; int retries = -1; // spin（！trylock（））{hashentry <k、v> f; if（retries <0）{//ヘッダーノードが空の場合、新しいノードを作成します（e == null）{if（node == null）{node = new Hashentry <K、v>（hash、key、value、null）; } retries = 0; //それ以外の場合は、リンクリストをトラバースしてノードを見つけます} else {e = e.next; } //ここに1を追加して、最大値を超えるかどうかを判断します} else if（++ retries> max_scan_retries）{lock（）;壊す; // retriesが偶数である場合、最初の変更が変更されたかどうかを決定しますRETRIES = -1; }} return node;} //スピンロック（操作を取り外して交換する）プライベートボイドスキャンアンドロック（オブジェクトキー、int hash）{//リンクリストのヘッダーノードをハッシュコードHashentry <k、v> first = entryhash（this、hash）に従ってリンクリストのヘッダーノードを取得します。 Hashentry <k、v> e = first; int retries = -1; // spin（！trylock（））{hashentry <k、v> f; if（retries <0）{//リンクリストを転送してノードを見つけますif（e == null || key.equals（e.key））{retries = 0; } else {e = e.next; } //ここに1を追加して、最大値を超えるかどうかを判断します} else if（++ retries> max_scan_retries）{lock（）;壊す; // retriesが偶数である場合、最初の変更が変更されたかどうかを決定しますRETRIES = -1; }}}前述したように、セグメント化されたロックの操作を配置、削除、交換するには、最初にロックを取得する必要があります。ロックを正常に取得した後にのみ、次の操作を実行できます。買収が失敗した場合、スピンが実行されます。 JDK1.7にもスピン操作が追加されています。スレッドの頻繁な一時停止と目覚めを避けるために、同時の操作中のパフォーマンスを改善できます。 ScanAndLockForputはPUTメソッドで呼び出され、スキャンアンドロックは削除および交換メソッドで呼び出されます。 2つのスピンメソッドはほぼ同じです。ここでは、ScanandLockForputメソッドのみを分析します。まず、ハッシュコードに基づいて、リンクリストのヘッダーノードを取得する必要があります。その後、スレッドはwhileループを入力して実行します。ループを終了する唯一の方法は、ロックを正常に取得することであり、この期間中はスレッドが吊り下げられません。ループが入力されたばかりの場合、RETRIRESの値は-1です。この時点で、スレッドはすぐにロックを取得しようとしません。代わりに、最初にキーに対応するノードが見つかります（発見されていない場合は、新しいものが作成されます）。次に再試行を0に設定します。次に、ロックを何度も取得しようとします。対応するRetries値は、最大試行回数が最大試行回数を超えるまで、毎回追加されます。ロックが取得されていない場合、ロック方法はブロックと取得のために呼び出されます。ロックを取得しようとする試み中に、ヘッダーノードが他の毎回変更されているかどうかを確認します（再試行は均一です）。変更された場合は、再試行を-1にリセットしてから、今すぐプロセスを繰り返します。これは、紡績時にスレッドが行うことです。スピン中にヘッドノードが変更されることが検出された場合、スレッドのスピンタイムが拡張されることに注意してください。
10.ハッシュテーブルを拡張するときにどのような操作が行われますか？
//再び@SuppressWarnings（ "Un -checked"）private void rehash（hashentry <k、v> node）{//古いハッシュテーブルの参照を取得<k、v> [] oldtable = table; //古いハッシュテーブルの容量を取得しますint oldcapacity = oldtable.length; //新しいハッシュテーブルの容量を計算します（古いハッシュテーブルの2倍）int newcapacity = oldcapacity << 1; //新しい要素のしきい値のしきい値を計算する=（int）（newcapacity * loadfactor）; //新しいハシェントリーアレイハッシュエントリー<k、v> [] newtable =（hashentry <k、v> []）new Hashentry [NewCapacity]; //新しいマスク値int sizemask = newcapacity -1; //古いテーブルのすべての要素を介した静けさ（int i = 0; i <oldcapacity; i ++）{//リンクリストのヘッダーノードを取得してくださいhashentry <k、v> e = oldtable [i]; if（e！= null）{hashentry <k、v> next = e.next; //新しいテーブルの要素のインデックスを計算しますint idx = e.hash＆sizemask; //次は、リンクリストに1つのノードのみがあることを示すために空です（next == null）{//ノードを新しいテーブルNewtable [idx] = e; } else {hashentry <k、v> lastrun = e; int lastidx = idx; // lastrunノードを配置し、ラストルンの後にノードを直接新しいテーブルに入れます（hashentry <k、v> last = next; last！= null; last = next）{int k = last.hash＆sizemask; if（k！= lastIdx）{lastIdx = k; lastrun = last; }} newTable [lastIdx] = lastrun; //リンクリストのLastrunノードの前に要素をトランシピングし、それらを新しいテーブルにコピーして（Hashentry <k、v> p = e; p！= lastrun; p = p.next）{v v = p.value; int h = p.hash; int k = h＆sizemask; Hashentry <k、v> n = newtable [k]; NewTable [k] = new Hashentry <K、V>（H、P.Key、V、N）; }}}}} //新しいテーブルInt nodeIndex = node.hash＆sizemaskの着信ノードの添え字を計算します。 //リンクリストnode.setNext（newTable [nodeIndex]）のヘッダーノードに着信ノードを追加します; //新しいテーブルを指定した添え字要素を着信Node NewTable [nodeIndex] = node; //新しいテーブルへのハッシュテーブル参照をポイントテーブル= newTable;}Rehashメソッドは、PUTメソッドで呼び出されます。 PUTメソッドが配置されると、新しい要素が作成され、ハッシュアレイに追加されることがわかります。ハッシュ競合の可能性が大きいほど、ハッシュテーブルのパフォーマンスも低下します。したがって、操作を行うたびに、要素の総数がしきい値を超えるかどうかを確認します。しきい値を超える場合、容量を拡大するために再ハッシュ法が呼び出されます。配列の長さを決定すると変更できなくなるため、元の配列を置き換えるために新しい配列を作成する必要があります。コードから、新しく作成された配列は元の配列の2倍の長さであることがわかります（oldcapacity << 1）。 After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。