各マスターは自分のツールを知っている必要があり、コレクションよりも頻繁に使用できるものは何ですか？ そのため、マルチスレッドコレクションの概要を少し作成し、 ConcurrentDictionaryから始めることにしました（大まかなレビューはすでにここで確認されていますが、ほとんどありません）。 一般に、.NET用のそのような記事がまだないことに多少驚いていました（ Javaには 十分です）。
行きましょう。
辞書自体に既に精通している場合は、次のセクションをスキップできます。
辞書<TKey、TValue>とは何ですか？
辞書は標準ハッシュテーブルの実装です。
ここで興味深いのは次の機能です。
初期化
初期化は、作成中（コレクションの初期サイズが転送される場合）または最初の要素が追加されるときに発生し、最も近い素数がサイズとして選択されます（3）。 この場合、2つの内部コレクション-int []バケットとEntry []エントリが作成されます 。 最初の要素には2番目のコレクションの要素のインデックスが含まれ、次の形式で要素自体が含まれます。
private struct Entry { public int hashCode; public int next; public TKey key; public TValue value; }
アイテムを追加する
要素を追加すると、そのキーのハッシュコードが計算され、次にコレクションサイズを法として追加されるバスケットインデックスが計算されます。
int bucketNum = (hashcode & 0x7fffffff) % capacity;
次のようになります。
次に、コレクションにそのようなキーが既に存在するかどうかを確認します。存在する場合、Add操作は例外をスローし、インデックスによる割り当ては要素を新しいものに単純に置き換えます。 辞書の最大サイズに達すると、拡張が行われます（新しいサイズは最も近い素数で選択されます）。
操作の複雑さは、それぞれO（n）です。
衝突が発生した場合（つまり、bucketNumインデックスを持つバスケットに既に要素が存在する場合）、新しい要素がコレクションに追加され、そのインデックスはバスケットに保存され、古い要素のインデックスは次のフィールドにあります。
したがって、 単方向リンクリストを取得します 。 この衝突解決メカニズムは、 チェイニングと呼ばれます 。 要素を追加するときに衝突の数が大きい場合（現在のバージョンでは100を超える）、コレクションが展開されると、 再ハッシュ操作が発生し 、その前に新しいハッシュコードジェネレーターがランダムに選択されます。
衝突の場合にO（1）またはO（n）を追加する難しさ。
アイテムを削除する
要素を削除するとき、その内容をデフォルト値で上書きし、必要に応じて他の要素の次のポインターを変更し、この要素のインデックスをfreeList内部フィールドに保存し、古い値を次のフィールドに保存します。 したがって、新しい要素を追加するときに、そのような空きセルを再利用できます。
衝突の場合の難易度は、O（1）またはO（n）です。
その他
また、2つの点に注目する価値があります。
1）辞書をクリーニングするとき、その内部サイズは変更されません。 つまり、潜在的に、単にスペースを無駄にしているだけです。
2）GetEnumeratorは、コレクション全体の反復子を返します（O（1）複雑度）。 要素のみを追加した場合、同じ順序で返されます。 ただし、要素を削除して新しい要素を追加した場合、それに応じて順序が変更されるため、それに依存しないでください（特に、フレームワークの将来のバージョンで変更される可能性があるため）。
ConcurrentDictionaryについてはどうでしょうか？
額には、スレッドの安全性を確保するための2つの解決策があるようです。辞書へのすべてのアクセスをロックでラップするか、そのすべてのメソッドをロックします。 ただし、明らかな理由により、このソリューションは遅くなります。ロックによって遅延が追加され、コレクションで動作する可能性のある1つのスレッドの制限によってパフォーマンスが向上することはありません。
Microsoftはより良い方法を採用し、Dictionaryはいくつかの変更を受けました。 したがって、辞書とそのバスケットの内部構造のおかげで、メソッドを使用して、それらに対してブロッキングが実行されます
private void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount) { bucketNo = (hashcode & 0x7fffffff) % bucketCount; lockNo = bucketNo % lockCount; }
同時に、すべてのバスケットが同じエントリ配列を使用するため、通常の辞書はこのスキームで動作できませんでした。したがって、バスケットは通常の単一のリンクリストになります。volatile Entry [] m_buckets （フィールドは非ブロッキングを提供するvolitale 1つのスレッドが何らかの操作を実行しようとしている状況での同期（現時点では他のスレッドがコレクションのサイズを変更する）。
その結果、バスケットは次のようになり始めました。
lockNoは、同期オブジェクト-object [] m_locksを含む新しい配列のインデックスです 。 その使用により、異なるスレッドが異なるバスケットを同時に変更できます。 このコレクションのサイズは、コンストラクターを介して設定できるパラメーターConcurrencyLevelに依存します。 コレクションと同時に動作するスレッドのおおよその数を決定します（デフォルトでは、これはプロセッサの数* 4です）。 この値が高いほど、操作の記述が容易になりますが、コレクション全体の完全なブロック（ Resize、ToArray、Count、IsEmpty、Keys、Values、CopyTo、Clear ）を必要とするはるかに高価な操作になります 。 このパラメーターは、1つのロックに収まるコレクションの要素の数も決定します（バスケットの数とこのコレクションのサイズの比として）。必要以上の要素がある場合、コレクションは拡張されます。そうでない場合、要素の検索にはO（1）が必要ですが、O （n）リンクされたリストを走査する。 コレクションの初期拡張の数をわずかに減らすために、辞書の初期サイズは3ではなく31です。
すべての操作は次の形式を取りました。
void ChangeBacket(TKey key) { while (true) { Node[] buckets = m_buckets; int bucketNo, lockNo; GetBucketAndLockNo(m_comparer.GetHashCode(key), out bucketNo, out lockNo, buckets.Length); lock (m_locks[lockNo]) { if (buckets != m_buckets) { // Race condition. , . continue; } Node node = m_buckets[bucketNo]; // . } } }
新しい要素を追加するときは、既にそのようなキーがあるかどうかを判断するためだけに、リンクされたリスト全体を移動しなければなりません。そうでない場合は追加します。 同様に、削除する場合-最初に、削除するノードを見つける必要があります。
ただし、一部の操作では、ロックは原則的に不要です 。これらはTryGetValue、GetEnumerator、ContainsKey、およびindexingです。 なんで？ バスケットのサイズのすべての変更はフィールドが揮発性であるために表示されるため、要素への追加または変更は新しい要素を作成して古い要素を置き換えることで行われ、削除は単にポインタを次のノードに置き換えることで行われます。
その他
1）通常のディクショナリとは異なり、 Clearメソッドを呼び出すと、コレクションサイズがデフォルト値にリセットされます。
2） GetEnumerator-メソッド呼び出し後に別のスレッドによって変更が行われた場合、およびイテレータがこの要素を渡した方法で古い値を返すことができます。 冒頭に述べた記事では、
dictionary.Values.ToArray（）よりもdictionary.Select（x => x.Value）.ToArray（）を使用した方が良いそして、これは完全に真実ではありません-「より良い」の代わりに「より速い」はずです-ロックがないため、これらのアプローチが異なるデータを返す可能性があることを考慮しなければなりません。
ご清聴ありがとうございました。
使用した記事：
1. .NET辞書
2. コンカレントコレクション内：ConcurrentDictionary
3. コンカレントコレクション
4. .NETリフレクター