.Netの同時辞書でGrowTableメソッド

Question

GrowTableメソッドでいくつかの魔法を説明できますか？

コード：他の.NETのコレクション（リスト、辞書）メソッドは、ダブルサイズを維持リサイズして

// Compute the new table size. We find the smallest integer larger than twice the previous table size, and not divisible by 
// 2,3,5 or 7. We can consider a different table-sizing policy in the future. 
int newLength; 
try 
{ 
    checked 
    { 
     // Double the size of the buckets table and add one, so that we have an odd integer. 
     newLength = buckets.Length * 2 + 1; 

     // Now, we only need to check odd integers, and find the first that is not divisible 
     // by 3, 5 or 7. 
     while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0) 
     { 
      newLength += 2; 
     } 

     Assert(newLength % 2 != 0); 
    } 
} 

。

See Code, 1478 line

Answer 1

あなたは可変長配列にデータを格納すると、それを成長させるためにどのくらいの決定は、基本的には時間と空間のトレードオフです。アレイを拡張する必要があるときはいつでも多くのメモリを割り当てて（したがって無駄にして）、配列のサイズを変更する必要がないため、実行時間が短縮されます。 （償却された時間の複雑さに関しては、x％の増加はどのxでも同じですが、実際の速度は異なります）。

通常、アレイの成長はいくらですか？添加）。例えば、.Net List<T>の現在のMS実装は、2倍のサイズに成長するが、C++ vector<T>の現在のMS実装は50％だけ増加する。

これはすべて、ハッシュテーブルベースの辞書のエントリコレクションに適用できます（これは、唯一の可能性ではありません）。しかし、バケツも考慮する必要があります。彼らは時空間のトレードオフがありますが、あなたはどんなサイズを選んだとしても、辞書は機能します。しかし、コレクションが大きければ大きいほど、衝突は少なくなります。衝突が少なくなると、検索時間が短縮されます。一定時間のルックアップが必要な場合、バケットの数はディクショナリ内の項目の数に線形に比例する必要があります。したがって、バケット配列のサイズをentries配列と同じにすることは理にかなっています。

もう1つのことがあります。ハッシュコードに構造体がある場合、この構造体が辞書に反映されないようにします。これにより、より多くの衝突が発生するためです。アカウントIDをハッシュキーとして使用したとします。また、IT部門のユーザーには0から、マーケティングでは200からなどのIDを割り当てます。バケット配列のサイズが100の場合、多くの衝突が発生し、ひどいパフォーマンスが得られます。配列のサイズが2または5で割り切れる場合は、衝突の数も増えます。

このため、バケット配列に最適なサイズはプライムです。次の最良のサイズはほぼプライム（数が少ない除数）です。かつてのように、トレードオフがあります。計算の素数は比較的遅いです。それをより速くするには、ほとんど素数が十分だと言うことができます。あるいは、いくつかの素数をあらかじめ計算することができます。

このようなトレードオフがありますが、最高のソリューションはありません。あなたの使用のために、あなたはそれらのすべてのパラメータを細かくチューニングし、最適なものを試してみることができます。しかし、図書館の作家は、全員、または少なくともほとんどの人に十分なものにする必要があります。そして、Dictionary<T>の著者は何らかの理由でConcurrentDictionary<T>の作者とわずかに異なったものを選んだ。

Dictionary<T>の現在のMS実装が使用する特定のアルゴリズムは、7,199,369までのいくつかの素数のテーブルを持つことです。現在のサイズの2倍より大きいプライムを常に使用します。少数の場合、テーブルからそのような素数を最小に選択します。より大きい数値の場合、このような素数を正確に計算します。