有谁知道通过组合散列函数来降低碰撞概率是否有真正的好处？我特别需要了解 32 位散列，即结合 Adler32 和 CRC32。 基本上，adler32(crc32(data)) 会产生比 crc32(data) 更小的碰撞概率吗？这里 的最后一条评论给出了一些有利于合并的测试结果，但没有提到来源。就我的目的而言，碰撞并不重要（即任务不涉及安全性），但如果可能的话，我宁愿尽量减少这种可能性。PS：我刚刚开始在散列的美妙世界中做很多关于它的阅读。抱歉，如果我问了一个愚蠢的问题，我什至还没有获得正确的“哈希方言”，可能我的谷歌搜索也很糟糕。谢谢。
问问题
1370 次
1 回答
7
像这样将它们串联起来是没有意义的。您正在将一个 32 位空间散列到另一个 32 位空间。
在第一步发生crc32碰撞的情况下，最终结果还是碰撞。然后在 adler32 步骤中添加任何潜在的冲突。所以它不可能变得更好，而只能是相同或更糟。
为了减少冲突，您可以尝试独立使用两个哈希来创建 64 位输出空间：
adler32(数据) << 32 | crc32（数据）
这样做是否有显着的好处，我不确定。
请注意，您提到的原始评论是独立存储哈希：
无论您使用哪种算法，都有可能出现误报。但是，您可以通过使用两种不同的散列算法将这些机会大大减少。如果您要计算并存储每个 url 的 CRC32 和 Alder32，则任何给定 url 对的两个哈希同时发生冲突的几率将大大降低。
当然，这意味着存储两倍的信息，这是原始问题的一部分。然而，有一种方法可以存储两组散列数据，这样它需要最少的内存（10kb 左右），同时提供与 Perl 散列几乎相同的查找性能（15 微秒/查找与 5 微秒相比）。
于 2009-08-24T16:33:54.487 回答