Вероятность столкновения при использовании 32-битного хэша

У меня есть 10-значное строковое поле в базе данных. Я использовал CRC32 для хэширования этого поля, но я беспокоюсь о дубликатах. Может ли кто-нибудь показать мне вероятность столкновения в этой ситуации?

p.s. мое строковое поле уникально в базе данных. Если число строковых полей составляет 1 миллион, то какова вероятность столкновения?

Ответы

Ответ 2

В случае, если вы цитируете, по крайней мере одно столкновение по существу гарантировано. Вероятность хотя бы одного столкновения составляет около 1 - 3x10 -51. Среднее количество столкновений, которое вы ожидаете, составит около 116.

В общем случае среднее число столкновений по k выборкам, каждый из которых случайным образом выбирается среди n возможных значений:

N(n,k)~=k(k-1)/(2n)

Вероятность, по крайней мере, одного столкновения:

p(n,k)~=1-e^(-k(k-1)/(2n))

В вашем случае n = 2 32 и k = 10 6.

Вероятность трехстороннего столкновения в вашем случае составляет около 0,01. См. День рождения.