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

Если сомневаетесь, давайте проверим расчеты!

Формула, которую дал ваш инструктор, действительно верна, если предположить, что все исходы равновероятны и независимы друг от друга. Вот небольшая программа на 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

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

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

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

Чтобы ответить быстро без лишних слов:

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

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

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

Конечно, в Википедии есть https://en.wikipedia.org/wiki/Birthday_problem .

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