哈希函数组合 - 碰撞风险是否有显着降低？

Question

有谁知道，如果有关于通过组合散列函数降低碰撞概率真正的好处？我特别需要了解关于32位哈希的知识，即结合Adler32和CRC32。 基本上，将ADLER32（CRC32（数据））产生比CRC32（数据）一个较小的碰撞概率？ 的最后注释here给出了一些测试结果赞成合并，但没有注明出处。 对于我的目的，碰撞并不重要（即任务不涉及安全性），但无论如何，如果可能的话我宁愿减少的可能性。 PS：我刚刚开始了哈希的奇妙世界，对此做了大量的阅读。对不起，如果我问了一个愚蠢的问题，我甚至还没有获得适当的“哈希方言”，可能我的谷歌搜索关于此问题也形成了很差。 谢谢。

Answer 1

这是没有意义的他们在这样的系列组合。您将一个32位空间散列到另一个32位空间。

在所述第一步骤中的CRC32碰撞的情况下，最后的结果仍然是一个碰撞。然后在adler32步骤中添加任何潜在的冲突。所以它不会变得更好，只能是相同或更糟。

减少冲突，你可以尝试像使用独立的两个散列创建一个64位的输出空间：

的Adler32（数据）< < 32 | crc32（数据）

这样做是否有明显的好处，我不确定。

注意你提到原来的注释是独立存储的哈希值：

哪种算法您使用有 将会是假 阳性一些机会。但是，通过使用两种不同的哈希算法，您可以将这些机会减少 相当大的余量 算法。如果您要计算 并针对每个网址存储CRC32和 Alder32，则对于任何给定的url对，两个哈希 的同时碰撞的几率极大地减少了 。

当然，这意味着存储两次作为 很多信息，这是你原来的问题的一部分 。然而，存在 是存储两组散列的 数据，使得它需要最少的 存储器（10KB左右），同时给予 几乎相同的查找性能的方式（15 微秒/查找相比5 微秒）作为Perl的哈希。