2

私の教授は、ハッシュ衝突の確率を説明する際にこのスライドを提供してくれました。

ここに画像の説明を入力

「誕生日のパラドックス」で同じ誕生日の確率を調べたところ、ウィキペディアなどでn=10の確率は11.7であることがわかりました。実際、彼の式を使って自分で見つけて計算したすべての値は、教授のスライドとは異なっていました。

私の質問は、彼が「衝突が発生する前に何人の生徒をテーブルにハッシュできるか」と尋ねるとき、それは 2 人の生徒が同じ誕生日である確率を計算することとは違うのですか?

もしそうなら、そのための公式はありますか？

それとも、彼のスライドが単に間違っていたのでしょうか?

4

4 に答える 4

1

迷ったら計算してみよう！

すべての結果の可能性が等しく、互いに独立していると仮定すると、インストラクターが示した公式は実際に正しいものです。以下は、少数の学生の衝突数の値を出力する小さな C プログラムです。

#include <stdio.h>

const int kNumBuckets = 365;
const int kMaxNumber  = 50;

int main() {
  double probability = 1.0;
  for (int i = 1; i <= kMaxNumber; i++) {
    probability *= (double)(kNumBuckets - i + 1) / kNumBuckets;

    if (i % 10 == 0) {
      printf("Collision probability with %2d students: %g\n", i, 1.0 - probability);
    }
  }
  return 0;
}

出力は次のとおりです。

Collision probability with 10 students: 0.116948
Collision probability with 20 students: 0.411438
Collision probability with 30 students: 0.706316
Collision probability with 40 students: 0.891232
Collision probability with 50 students: 0.970374

これらの数値はあなたの教授と一致しませんが、ウィキペディアと一致します。これはあなたの教授の資料の単なる誤りだと思います。おそらく正直なミスなので、彼らに連絡して説明を求めても害はないかもしれません.

于 2016-06-13T20:02:31.990 に答える
0

苦労せずにすばやく答えるには：

私の質問は、彼が「衝突が発生する前に何人の生徒をテーブルにハッシュできるか」と尋ねるとき、それは 2 人の生徒が同じ誕生日である確率を計算することとは違うのですか?

いいえ、違いはありません。1..365 年の日付は、365 個のハッシュ バケットを持つ場合とまったく同じであり、許容されるハッシュ関数には完全にランダム化された値が含まれます (これは誤って、誕生日の問題でも想定されています)。

もしそうなら、そのための公式はありますか？

確かに、ウィキペディアにはhttps://en.wikipedia.org/wiki/Birthday_problemがあります。

于 2016-06-14T13:35:58.817 に答える
0

あなたの教授は、M = 181 または 182、つまり半年で計算を行ったと思います。これらの値で計算を実行すると、

181, 10, 0.22359889333483407
181, 20, 0.6636461635832673
181, 30, 0.9215808021897809
181, 40, 0.9905555232124136
182, 10, 0.2224990010873642
182, 20, 0.6615484583220019
182, 30, 0.9204086626783813
182, 40, 0.9902893472869162
于 2016-06-15T06:01:54.603 に答える