Как рассчитать шансы столкновения в хеш-алгоритмах?

Question

Скажем, у меня есть алгоритм хеширования, и он приятный и плавный (шансы появления любого одного значения хеша такие же, как у любого другого значения).

Теперь скажите, что я знаю, что шансы выбрать 2 хэша и столкновение составляют (Ради аргумента) 50000: 1.

Теперь скажите, что я выбрал 100 хешей. Как рассчитать шансы на столкновение в этом наборе из 100 значений, учитывая шансы на столкновение в наборе 2?

Каково общее решение этого, чтобы я мог придумать несколько попыток хэширования, после которых шансы падают ниже некоторого приемлемого порога? Например. Я могу сказать такие вещи, как «партия из 49999 созданий хеш-значений имеет высокую вероятность столкновения».

Answer 1

Это обобщение проблемы Дня Рождения .

Answer 2

Сначала вычислите вероятность того, что столкновения нет:

hashes_picked = 100
single_collision_odds = 50000

# safe_combinations is number of ways to pick hashes that don't overlap
safe_combinations = factorial(single_collision_odds) / factorial(single_collision_odds - hashes_picked)

# all_combinations is total number of ways to pick hashes
all_combinations = single_collision_odds ** hashes_picked   

collision_chance = (all_combinations - safe_combinations) / all_combinations

Answer 3

Для меня это звучит очень похоже на парадокс дня рождения .

Вы должны иметь возможность просто заменить набор возможных дней рождения (365) возможными хэшами (50000) и выполнить те же вычисления, которые они там представляют.

Если вы измените скрипт python, представленный в статье, для своих значений:

 def bp(n, d):
    v = 1.0
    for i in range(n):

         v = v * (1 - float(i)/d)
    return 1 - v

 print bp(2, 50000)

Вы получите шансы на столкновение с двумя числами 0,00002. Около 265 образцов, у вас есть около 50% вероятности столкновения.

Answer 4

Это называется проблема дня рождения . Чтобы решить эту проблему, подумайте о вероятности возникновения нет столкновений (назовите это p _nc ).

• p _nc (1) = 1
• p _nc (2) = 1 - p _c (2)
• p _NC (3) = p _NC (2) * p _NC (2) * p _NC (2)

Answer 5

и в JS

function calculate(n,k)
{

    var result =1;
    for (var i=0; i<k; i++){
        result=result*n/(n-i)
    }
    result=(1-1/result)*100;
    return result;
}