我有一个数据库驱动的 Web 应用程序，其中所有数据行的主键都被混淆如下:SHA256(内容类型 + 主键 + secret )，截断为前 8 个字符。内容类型是一个简单的词，例如“post”或“message”， secret 是一个 20-30 个字符的 ASCII 常量。结果存储在单独的索引列中，以便快速查找数据库。
在这种情况下如何计算哈希冲突的概率？我根本不是数学家，但一位 friend 声称，由于生日悖论，10,000 行的碰撞概率约为 1%，并截断 8 个字符。这种说法有道理吗？
最佳答案
是的，存在碰撞概率，而且可能有点太高了。确切的概率取决于“8 个字符”的含义。
“8 个字符”是指:
将二进制数据存储为 A) 十六进制或 D) 二进制字节，将是我的首选选项。但是我绝对建议您重新考虑您的“ key 混淆”方案或显着扩大存储的 key 大小以减少(目前过度) key 冲突的可能性。
来自维基百科:http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem
这种更一般意义上的生日问题适用于散列函数:在发生冲突之前可以生成的 N 位散列的预期数量不是 2^N，而是只有 2^(N/2)。
由于以上对您的设计的最保守的理解(将其读作 A，8 个十六进制字符 == 32 位)，如果您的方案以 ~64,000 行的规模存储，则预计会发生冲突。我认为这样的结果对于所有严肃的甚至是玩具的系统都是 Not Acceptable 。
交易表可能有数量，允许业务增长，从 1000 - 100,000 交易/天(或更多)。系统应设计为运行 100 年(36500 天)，并内置 10 倍的增长因子，因此..
为了让您的键控机制真正强大且专业有用，您需要能够将其扩展到可能处理约 360 亿 (2^35) 行而不会发生冲突。这意味着 70+ 位的哈希。
例如，源代码控制系统 Git 存储 160 位 SHA-1 哈希(40 个十六进制字符 == 20 字节或 160 位)。如果存储的不同文件修订少于 2^80 个，则预计不会发生冲突。
一种可能的更好的设计可能是，而不是完全散列和伪随机化 key 并希望(反对希望)避免冲突，而是将 8-10 位散列的 8-10 位添加到 key 中。
这将生成一个更大的 key ，包含原始 key 的所有唯一性加上 8-10 位验证。然后将验证访问 key 的尝试，超过 3 个无效请求将被视为通过“探测” key 空间而试图违反安全性并触发半永久锁定。
这里唯一的主要成本是适度减少给定 int 大小的可用 key 空间的大小。进出浏览器的 32 位 int 将有 8-10 位专用于安全性，因此将 22-24 位留给实际 key 。因此，您会在不够用的情况下使用 64 位整数。
关于math - 与截断的 SHA-256 哈希发生冲突的概率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19962424/