为何CRC64哈希的布隆过滤器实际误判率远高于理论值？

布隆过滤器的预期误判率理论公式为：
p(false) = (1 - (1 − 1/m)ᵏⁿ)ᵏ
通过仿真验证哈希函数随机性时，SipHash的结果与理论值完全吻合，但采用不同种子作为前缀的CRC64哈希时，仿真误判率（0.0308875）远高于理论值（5.73158e-06），其深层原因可从以下几点分析：

• CRC64的线性本质破坏哈希独立性
  CRC64是基于线性反馈移位寄存器（LFSR）实现的线性哈希函数，其输出与输入存在严格的线性映射关系：对于任意输入A和B，CRC(A XOR B)可通过CRC(A)和CRC(B)的线性组合计算得到。当用不同种子作为前缀生成多个哈希函数时，每个哈希输出本质是CRC(seed_i || data)，而根据CRC的线性特性，该值等价于CRC(seed_i)与CRC(data)的线性组合（含少量格式修正项）。这导致k个哈希函数的输出并非独立随机，而是存在强相关性，完全违背了布隆过滤器对k个哈希函数两两独立的核心假设。

• 种子前缀的构造未生成真正独立的哈希映射
  给原始数据添加不同种子前缀的方式，并没有为每个哈希函数创建独立的映射空间。由于CRC的线性性，多个哈希输出只是对原始数据CRC值的简单异或/移位变换，彼此之间的桶位选择高度重叠：比如，两个不同种子对应的哈希函数，可能会将同一数据映射到存在固定偏移的桶位上，而非均匀随机的独立位置。这种重叠会导致布隆过滤器中被置位的桶位分布远不如理论均匀，误判概率自然大幅上升。

• 理论误判率公式的前提假设失效
  理论公式的推导依赖两个关键前提：一是每个哈希函数将元素均匀映射到m个桶；二是k个哈希函数的映射结果相互独立。当使用带种子前缀的CRC64时，第二个前提完全不成立：由于哈希输出的强相关性，同一元素对应的k个桶位并非独立被置位，实际的桶位重叠概率远高于理论预期，直接导致误判率偏离计算值。

• SipHash的设计特性对比
  SipHash是专为提供独立、均匀哈希输出设计的伪随机函数，其内部包含多轮非线性混淆操作（异或、加法、循环移位的组合），能够彻底打破输入之间的线性依赖。即使输入仅存在种子前缀的差异，SipHash也能生成高度独立的哈希值，完全满足布隆过滤器的假设条件，因此仿真结果与理论值一致。

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