Насколько вы можете обрезать SHA1-хэш и быть уверенным в наличии уникального идентификатора?
Две вещи приходят на ум:
- Контекст существен. Если Вы - игровой программист или в технической дисциплине, то математика может быть жизненно важной для Вашего задания. Я делаю базу данных и веб-разработку, поэтому математика уровня средней школы хорошо для меня.
- Вы, очень вероятно, будете снова использовать чужой предварительно созданный математический код вместо изобретения велосипед, особенно в полях как шифрование и сжатие. (Это может также применяться, если Вы находитесь в игровой разработке с помощью стороннего инструмента физики или 3D механизма.) Наличие платформы проверенных на практике стандартных программ для использования в Ваших программах предотвращает ошибки и потенциальные слабые места безопасности - определенно хорошая вещь.
2 ответа
Адаптируя формулы в википедии для задачи «День рождения» , вы можете аппроксимировать вероятность столкновения как e^(-n^2/(2^(b+1))), где n - количество документов, а b - количество бит. График этой формулы с n = 100,000 , похоже, вы захотите b> 45 по крайней мере. Я был бы более склонен пойти с 64, чтобы сделать это хорошее и круглое число. Тем не менее, есть ли у вас план действий в случае коллизий, если они происходят (может быть, немного изменить временную метку или добавить одноразовый номер?)
В этом отношении, если sha1 основан не только на содержимом документ, почему бы просто не сделать его случайным идентификатором? В этом случае столкновения представляют меньшую проблему, поскольку вы всегда можете сгенерировать новое случайное число и повторить попытку (однако вероятность столкновения с одной попыткой одинакова).
Ну, вот, возможно, слишком упрощенный ответ ..
Если с полным sha1 вы получаете примерно 1 из 2 ^ 160 шансов на столкновение, то путем усечения одного символа вы увеличиваете вероятность столкновения на 16 (все возможные значения усеченного символа) ... что составляет 2 ^ 4. Итак, если вы урежете x символов, вы получите 1 из 2 ^ (160 - 4 * x) шансов на столкновение .. верно?