以下のスニペットは、ランダムな double をディクショナリに追加します。これが確実に失敗したことに驚きました。20K ～ 50K の挿入後の辞書での魔女の衝突 (走行距離は異なる場合があります)。
このパターンはランダムなのか、それともすぐに重複を引き起こすハッシュなのか? 以下のコードはほとんど実行されません。はるかに大きいハッシュ範囲では、次のようになるとは思いもしませんでした:
var rnd = new Random();
var dict = new Dictionary<double, int>();
for (int i = 0; i< 100000; i++)
{
var nbr = rnd.NextDouble();
dict.Add(nbr, i); //fails at some point
}
これは誕生日のパラドックスによるものです。Random は 32 ビットのシードを使用しており、表から、約 77k の値を生成した後、32 ビット空間内で 50% の確率で衝突が発生することがわかります。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加