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

这些数字与您的教授不一致，但与 Wikipedia 一致。我假设这只是你教授材料中的一个错误。联系他们并要求澄清可能没有什么坏处，因为这可能只是一个诚实的错误。

于 2016-06-13T20:02:31.990 回答
0

我评估了你教授的表达方式。你的好眼光：我不明白你发布的价值观。我看到的更接近生日问题的结果。你是一个善于思考而不是接受你被告知的一切的好学生。

/**
 * Implement the expression in the question to check.
 * User: mduffy
 * Date: 6/14/2016
 * Time: 8:03 AM
 * @link http://stackoverflow.com/questions/37798077/how-many-students-can-you-put-into-a-hash-table-before-a-collision-occurs
 */
public class CollisionProbability {

    public static void main(String[] args) {
        int m = (args.length > 0) ? Integer.parseInt(args[0]) : 365;
        int nMin = 10;
        int nMax = (args.length > 1) ? Integer.parseInt(args[1]) : 100;
        int dn = (args.length > 2) ? Integer.parseInt(args[2]) : 10;
        for (int n = nMin; n < nMax; n += dn) {
            System.out.println(String.format("m=%d n=%d p(collide)=%f", m, n, p(m, n)));
        }
    }

    public static double p(int m, int n) {
        double p = 1.0;
        for (int i = 1; i < n; ++i) {
            p *= (double)(m-i)/m;
        }
        return 1.0-p;
    }
}
于 2016-06-14T12:18:16.803 回答
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 回答