algorithm - 您可以截断多少 SHA1 散列并合理确定拥有唯一 ID？

Question

我正在制作一个存储文档的应用程序，并根据包括时间戳在内的一些内容的 SHA1 摘要为每个文档提供一个 UID。摘要有很多字符，我想让用户使用完整摘要的前 x 个字符来识别文档。如果文档数量可能在 10K - 100K 左右，x 的合适值是多少？

Answer 1

在 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？在这种情况下，碰撞问题不大，因为您始终可以生成一个新的随机数并重试(但是，单次尝试发生碰撞的概率是相同的)。