これは少し主観的な質問ですが、これに答えるために最善を尽くします (CLR 4.0 の辞書に変更があったかどうかはまだ調査していないため、CLR 2.0 の観点からのみ)。
文字列をキーにした辞書を使用しています。考えられる文字列は無限に存在する可能性があるため、考えられるすべてのハッシュ コードは「可能性が等しい」と仮定するのが合理的です。言い換えれば、2^32 ハッシュ コード (int の範囲) のそれぞれが、文字列クラスに対して同様に可能性が高いということです。BCL の Dictionary の現在のバージョンは、このようにして取得した 32 ビット ハッシュ コードから 32 番目のビットを削除し、本質的に 31 ビット ハッシュ コードを取得します。したがって、私たちが扱っている範囲は、2^31 個の一意の可能性が等しいハッシュ コードです。
ハッシュ コードの範囲は、辞書に含まれる、または含まれる可能性のある要素の数に依存しないことに注意してください。
辞書クラスは、このハッシュ コードを使用してバケットを「Myclass」オブジェクトに割り当てます。したがって、基本的に、2 つの異なる文字列が同じ 31 ビットのハッシュ コードを返す場合 (BCL 設計者が文字列ハッシュ関数を非常に賢明に選択したと仮定すると、そのようなインスタンスはかなり分散するはずです)、両方に同じバケットが割り当てられます。このようなハッシュ衝突では、何もできません。
さて、Dictionary クラスの現在の実装では、異なるハッシュ コード (これも 31 ビット) でさえ、同じバケットで終わる可能性があります。バケット インデックスは次のように識別されます。
hash = <31 bit hash code>
pr = <least prime number greater than or equal to current dictionary capacity>
bucket_index = hash modulus pr
したがって、フォーム (pr*factor + bucket_index) のすべてのハッシュ コードは、factor 部分に関係なく、同じバケットになります。
可能性のあるすべての 31 ビット ハッシュ コードが最終的に異なるバケットになることを確実にしたい場合、唯一の方法は、pr を可能な限り最大の 31 ビット ハッシュ コード以上にすることです。つまり、すべてのハッシュ コードが (pr*0 + hash_code) の形式であることを確認してください。つまり、pr は 2^31 よりも大きくなければなりません。これは拡張により、辞書の容量が少なくとも 2^31 であることを意味します。
ハッシュの衝突を最小限に抑えるために必要な容量は、ディクショナリに格納する要素の数にはまったく依存せず、可能なハッシュ コードの範囲に依存することに注意してください。
ご想像のとおり、2^31 は非常に大きなメモリ割り当てです。実際、容量として 2^31 を指定しようとすると、長さ 2^31 の配列が 2 つになります。32 ビット マシンでは、RAM の可能な最大アドレスは 2^32 であることを考慮してください!!!!!
何らかの理由で、ディクショナリのデフォルトの動作が受け入れられず、ハッシュの衝突 (または、バケットの衝突と言うべきです) を最小限に抑えることが重要な場合は、独自のハッシュ コードを提供することだけを望みます (つまり、文字列をキーとして使用しないでください)。このようなハッシュ コードでは、バケット インデックスを取得するための式を念頭に置いて、可能なハッシュ コードの範囲を最小限に抑えるように努める必要があります。最も簡単な方法は、番号/インデックスを一意の MyClass インスタンスに段階的に割り当て、この番号をハッシュ コードとして使用することです。次に、辞書容量として MyClass インスタンスの総数を指定できます。ただし、このような場合、オブジェクトの「インデックス」とインデックスがインクリメンタルであることを知っているため、辞書の代わりに配列を簡単に維持できます。
最後に、「数え切れないほどのサイズ変更はありません」という他の人が言ったことを繰り返したいと思います。ディクショナリは、容量が不足するたびに容量を 2 倍にします (新しい容量以上の最も近い素数に丸めます)。いくらかの処理を節約するために、容量を MyClass インスタンスの数に適切に設定できます。いずれにせよ、辞書はインスタンスを格納するためにこの容量を必要としますが、これは「ハッシュ衝突」を最小化せず、通常の状況では十分に速い。