ConcurrentHashMapでセグメントがどのように定義されているか

Question

こんにちは私はJava Concurrencyが初めてです。以下の2つの質問があります。

Q.1コンカレントハッシュマップでセグメントがどのように定義されていますか？つまり、MapとConcurrencyLevelの値が16である（同時に動作できるスレッドが16個ある）場合、セグメントの定義方法は？ Qはそれぞれ16個のセグメントが等しく、それぞれに4個の要素がありますか？それとも不均等なサイズのセグメントですか？

Q.2。初期容量が62、ConcurrencyLevelが16のConcurrentHashMapを定義した場合、そのマップに62要素を置くとします。私の理解によれば、それぞれ4つの要素を持つ15のセグメントがあり、16のセグメントは2つの要素を持つでしょうか？私はここで正しいですか？セグメントの定義方法のConcurrentHashMapで

事前に感謝

Answer 1

Q.1？つまり、MapとConcurrencyLevelの値が16である（同時に動作できるスレッドが16個ある）場合、セグメントの定義方法は？ Qはそれぞれ16個のセグメントが等しく、それぞれに4個の要素がありますか？それとも不均等なサイズのセグメントですか？

ANS - 16を同時性レベルとして定義した場合、16個のセグメントが作成されます。

各セグメントは内部的にHashTable S [0] - > HASHTABLE（）を保持します。

したがって、要素数が64の場合、ハッシュ（キー）はセグメント番号を計算します。セグメント番号は、等しくないサイズのセグメントすべてを持つことがあります。セグメントハッシュコードは、（0〜15）の間の任意の数値を返すように計算されます。

Q.2。初期容量が62、ConcurrencyLevelが16のConcurrentHashMapを定義した場合、そのマップに62要素を置くとします。私の理解によれば、それぞれ4つの要素を持つ15のセグメントがあり、16のセグメントは2つの要素を持つでしょうか？私はここで正しいですか？

ANS-上記で説明したように、セグメントの選択は計算されたハッシュコードに基づいて行われるため、16セグメントがすべて同じサイズになることは確実ではありません。

Answer 2

ConcurrentHashMapの実装では、基本的に2レベルのハッシュテーブルであるセグメント（すべてではない）を使用していると考えてください。キーがKで、キーのハッシュコードがh = K.hashCode()の場合、通常のハッシュマップと同様に、hを使用して16セグメントの配列にハッシュコードを作成します（例：h % 16など）。これにより、キーが存在するセグメントが得られます。これは別のマップです。このマップ内でキーを検索するには、hを再度使用してください。

違いは、通常put()のような突然変異操作中に発生するすべてのロック操作は、関連するセグメントをロックするだけで、他の操作は並行して進めることができるということです。セグメントが均等に容量に大きさで

Q1が、要素のためのセグメントを使用して選択されているので、彼らは、一般的には、要素の不均等な数を持っています：

は、特にご質問にお答えするために、異常な場合を除いて完全に一様にならないハッシング。HashMapの配列の最初の半分が後半と同じ要素数を持っているかどうかを尋ねた場合と同じです。平均で期待要素の数は同じですが、任意のHashMapことが原因のランダムな変化に、両方の半分の要素の正確同じ番号を持つことが非常にとは異なります。

Q2

いいえ、マップはそのようにレイアウトされることはありません。上記のように、セグメントへの要素の選択は、（良好なハッシュ関数のために）セグメントが本質的にランダムに選択されることを意味するハッシュを使用して行われる。 1から16までのボールが入っているとしたら、ボールを一度に62回選んでボールを交換する前の番号を記録したとします。あなたは4, 4, 4, 4, 4, 4, 4, 4, 4, ... , 4, 2, 2]のような配信を期待しません！それはもっとランダムです。