我正在制作一个存储文档的应用程序,并根据包括时间戳在内的一些内容的 SHA1 摘要为每个文档提供一个 UID。摘要有很多字符,我想让用户使用完整摘要的前 x 个字符来识别文档。如果文档数量可能在 10K - 100K 左右,x 的合适值是多少?
最佳答案
在 wikipedia for the Birthday problem 上调整公式,您可以将碰撞概率近似为 1 - e^(-n^2/(2^(b+1)))
,其中 n
是文档计数b
是位数。 Graphing this formula with n=100,000 ,看起来您至少需要 b > 45。我更倾向于使用 64 来使它成为一个漂亮的整数。也就是说,如果发生冲突,是否有处理冲突的计划(可能稍微更改时间戳,或添加随机数?)
就此而言,如果 sha1 不仅仅基于文档的内容,为什么不简单地使它成为一个随机 ID?在这种情况下,碰撞问题不大,因为您始终可以生成一个新的随机数并重试(但是,单次尝试发生碰撞的概率是相同的)。
关于algorithm - 您可以截断多少 SHA1 散列并合理确定拥有唯一 ID?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4784335/