.Netディクショナリが素数にサイズ変更されるのはなぜですか？

Question

this questionに従って.Net辞書は、現在のサイズの少なくとも2倍の素数に割り振られたスペースをリサイズします。現在のサイズの2倍だけでなく、素数を使用することが重要なのはなぜですか？ （私は答えを見つけるために私のgoogle - fuの力を使用しようとしましたが、役に立たない）

Answer 1

choosing a good hashing functionに関するアルゴリズム実装の詳細であり、均一な分布を提供します。不均一な分布は、衝突の数およびそれらを解決するコストを増加させる。

Answer 2

これは素数の数学のためです。彼らは異なる小さな数字に因数分解することはできません。保存されたアイテムからハッシュ番号を分割すると、均等な分布が得られます。オブジェクトに応じて素数を持たない場合、分布は均一ではない可能性があります。

Answer 3

要素が配置されるバケットは、(hash & 0x7FFFFFF) % capacityによって決まります。これは、一様に分散する必要があります。このことから、baseとcapacityが互いに素でない（最大公約数> 1）特定の基底（hash1 = x1 * base、hash2 = x2 * base、...）の倍数である複数のエントリが使用され、いくつかのスロットが過度に使用され、中古。素数はそれ自身を除いて任意の数になるので、良い分布を達成する可能性は比較的高い。

これの特に優れた特性は、capacity > 30の場合、各ビットのハッシュコードへの寄与が異なることです。したがって、ハッシュのバリエーションがほんの数ビットに集中すると、それでも良好な分布につながります。これは、なぜ2のべき乗である容量が悪いのかを説明します。高いビットをマスクします。上位ビットだけが異なる数の集合はそうは考えにくい。

個人的に私は彼らがその機能をひどく選ぶと思います。これには高価なモジュロ演算が含まれており、エントリが素数の倍数であればその性能は低下します。しかし、それはほとんどのアプリケーションにとって十分であるようです。