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

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

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

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

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

Ответ 1

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

Ответ 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

Ответ 3

Это похоже на Парадокс дня рождения для меня.

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

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

 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% вероятность столкновения.

Ответ 4

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

p _nc (1) = 1
p _nc (2) = 1 - p _c (2)

> (2)

Ответ 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;
}