У меня есть 10-значное строковое поле в базе данных. Я использовал CRC32 для хэширования этого поля, но я беспокоюсь о дубликатах. Может ли кто-нибудь показать мне вероятность столкновения в этой ситуации?
p.s. мое строковое поле уникально в базе данных. Если число строковых полей составляет 1 миллион, то какова вероятность столкновения?
Дубликат Ожидаемые столкновения для совершенного 32-битного crc
Ответ ссылается на эту статью: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670
Найдено изображения ниже: http://preshing.com/20110504/hash-collision-probabilities
В случае, если вы цитируете, по крайней мере одно столкновение по существу гарантировано. Вероятность хотя бы одного столкновения составляет около 1 - 3x10 -51. Среднее количество столкновений, которое вы ожидаете, составит около 116.
В общем случае среднее число столкновений по k выборкам, каждый из которых случайным образом выбирается среди n возможных значений:
Вероятность, по крайней мере, одного столкновения:
В вашем случае n = 2 32 и k = 10 6.
Вероятность трехстороннего столкновения в вашем случае составляет около 0,01. См. День рождения.