非相关的两个32位哈希与单个64位哈希的碰撞率是否相同？

经常有人问我这类问题：“两个16位哈希的碰撞率是不是和单个32位哈希一样？”或者“把两个32位哈希凑一块儿，抗碰撞性能比得上单个64位哈希吗？”大部分业内的回答都是：只要这俩是性能良好且完全非相关的哈希函数，那答案就是肯定的。但这句话到底藏着啥门道？今天就唠清楚，顺便说说MurmurHash里的一个有趣细节。

先搞懂核心逻辑：独立事件的概率叠加 #

说白了，这里的关键是「独立」二字。如果两个哈希函数满足两个条件：

• 各自都是性能良好的哈希：输出均匀分布，没有明显的碰撞偏向
• 完全非相关：一个哈希的输出结果和另一个毫无关联，不会因为输入相同就出现某种固定的联动规律

那把它们的结果拼接起来后，整体的碰撞概率就和一个长度为两者位数之和的单哈希完全一致。举个例子：

• 单个16位哈希的碰撞概率是 1/2^16
• 两个独立的16位哈希要同时碰撞，概率就是 (1/2^16) * (1/2^16) = 1/2^32，这和单个32位哈希的碰撞概率完全相同。

反例：MurmurHash2_x86_64的“伪并行”问题 #

MurmurHash3的作者曾提到过一个点：MurmurHash2_x86_64版本为了提速，会并行计算两个32位的中间结果，最后再简单混合输出。这种设计确实能让计算速度更快，但这里有个致命的问题——这两个32位结果并不是来自两个独立的哈希函数！

它们是基于同一个输入，用几乎相同的计算逻辑并行处理出来的，输出结果存在内在的关联性，完全不符合“非相关”的要求。所以它的抗碰撞性其实达不到单个64位哈希的水平，因为两个32位结果的碰撞不是独立事件，整体碰撞概率会比理想的 1/2^64 要高不少。

总结一下 #

别光看“两个短哈希等价一个长哈希”这句话，一定要抓住前提：必须是两个完全独立、无关联的良好哈希函数。如果只是同一个算法内部拆分出来的并行计算，本质上还是同一个哈希的变体，抗碰撞性自然会打折扣。

内容的提问来源于stack exchange，提问作者bryc