Сколько учеников вы можете положить в хэш-таблицу до столкновения?

Question

Мой профессор дал нам этот слайд, объясняя Hash Collision вероятности:

Когда я посмотрел вероятности двух людей, имеющих один и тот же день рождения в «День рождения Paradox», я нашел на Wikipedia and other sources, что вероятность при n = 10 должно быть 11,7. На самом деле каждое значение, которое я нашел и рассчитал, используя его формулу, отличается от слайда профессора.

Итак, мой вопрос: когда он спрашивает: «Сколько учеников мы можем занести в наш стол перед столкновением», разве это не так, как рассчитывать вероятность того, что у каждого из двух учеников будет тот же день рождения?

И если да, то есть ли формула для этого?

Или его слайд был просто неправильным?

Answer 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 

Эти цифры не согласны с профессором, но они соглашайтесь с Википедией. Я собираюсь предположить, что это всего лишь ошибка в материалах вашего профессора. Может быть, это не помешает связаться с ними и попросить разъяснения, так как это, вероятно, просто честная ошибка.

Answer 2

Я оценил выражение, которое дал ваш профессор. Хороший глаз от вас: я не получаю ценности, которые вы опубликовали. Те, которые я вижу, ближе к результатам проблемы с днем ​​рождения. Вы хороший ученик, чтобы думать и не принимать все, что вам сказали.

/** 
* 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; 
    } 
} 

Answer 3

Чтобы быстро ответить без лишнего шума:

Так что мой вопрос: когда он спрашивает: «Сколько студентов мы можем хэширование в нашу таблицу, прежде чем происходит столкновение,» является то, что отличается от вычисления вероятность того, что у каждого из двух учеников одинаковый день рождения?

Нет, это не так. Дни года 1..365 точно совпадают, имея 365 хэш-кодов, а допустимая хеш-функция содержит совершенно рандомизированные значения (что также ошибочно принято в проблеме дня рождения).

И если да, то есть ли формула для этого?

Уверенный, Википедия имеет https://en.wikipedia.org/wiki/Birthday_problem.

Answer 4

Я думаю, что ваш проф сделал свои расчеты с 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