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

Question

有谁知道通过组合散列函数是否有降低碰撞概率的真正好处？我特别需要知道32位散列,即组合Adler32和CRC32. 基本上,adler32(crc32(data))会产生比crc32(数据)更小的碰撞概率吗？这里 的最后一条评论给出了一些有利于组合的测试结果,但没有提到任何来源.出于我的目的,碰撞并不重要(即任务不涉及安全性),但如果可能的话,我宁愿尽可能地减少概率.PS:我刚开始在哈希的精彩世界里,做了很多关于它的阅读.对不起,如果我问一个愚蠢的问题,我还没有获得正确的"哈希方言",可能我的谷歌搜索也很差.谢谢.

Answer 1

将它们串联组合是没有意义的.您正在将一个32位空间散列到另一个32位空间.

在第一步中发生crc32碰撞的情况下,最终结果仍然是碰撞.然后,在adler32步骤中添加任何潜在的碰撞.所以它不会变得更好,只能是相同或更糟.

要减少冲突,您可以尝试单独使用两个哈希来创建64位输出空间:

adler32(data)<< 32 | CRC32(数据)

这样做是否有显着的好处,我不确定.

请注意,您引用的原始注释是独立存储哈希值:

无论你使用哪种算法,都会有一些误报的可能性.但是,通过使用两种不同的散列算法,您可以大幅减少这些机会.如果您要为每个URL计算并存储CRC32和Alder32,则对于任何给定的URL对,两个哈希的同时冲突的几率会大大降低.

当然,这意味着存储两倍于原始问题的信息.然而,存在一种存储两组散列数据的方式,使得它需要最少的内存(10kb左右),同时提供与Perl的散列几乎相同的查找性能(15微秒/查找相比5微秒).