32位哈希函数碰撞检测中基于样本量的异常阈值缩放问题

嘿，这个问题我太有共鸣了——当初测试哈希碰撞概率的时候，我也踩过用百分比偏差判断异常的坑！确实，直接对比观测碰撞数和理想值的百分比差会被样本量带偏：小样本下的“大幅百分比偏差”和大样本下的“小幅百分比偏差”，实际对应的出现概率可能是差不多的，根本没法直接用百分比来划异常阈值。

为什么百分比偏差不靠谱？ #

你已经算出了理想碰撞数（均值）：
$$\mu = \frac{n^2-n}{2(2{32})}$$
这个碰撞数的分布其实可以用泊松分布来近似（当n远小于2³²时，也就是单个输入碰撞的概率极低，事件近似独立）。而泊松分布有个关键特性：方差等于均值，也就是说它的标准差是$\sigma = \sqrt{\mu}$。

你用的百分比偏差公式是$\frac{obs-\mu}{\mu} \times 100%$，这个其实等于$\frac{Z}{\sqrt{\mu}}$（其中Z是标准分数，也就是偏离均值的标准差倍数）。所以当$\mu$越大（样本量越大），相同的Z对应的百分比偏差就越小——这就是你看到的现象：小样本下53%的偏差和大样本下12%的偏差，可能对应着差不多的偏离概率。

正确的归一化方法：用Z分数（标准分数）判断偏离程度 #

要摆脱样本量的影响，应该用Z分数来衡量观测值的偏离程度，公式是：
$$Z = \frac{observed_collisions - \mu}{\sqrt{\mu}}$$

Z分数表示观测值偏离均值的标准差倍数，不管样本量多大，相同的Z分数对应的出现概率是一致的：

• Z=2：观测值比均值高2个标准差，对应的单侧出现概率约2.28%，属于比较少见的情况
• Z=3：观测值比均值高3个标准差，对应的单侧出现概率约0.13%，可以作为严格的异常阈值
• 你可以根据自己的需求选择合适的Z值，比如选Z=2.58对应0.5%的单侧概率，作为异常的分界线

用你的例子实际计算验证 #

我们拿你给出的两个例子算一下：

1. 当n=466550时，$\mu=25.34$，$\sigma=\sqrt{25.34}≈5.03$，观测碰撞数39：
   $$Z = \frac{39-25.34}{5.03}≈2.72$$
   对应的单侧出现概率约0.33%，属于比较罕见的情况。

2. 当n=1470580时，$\mu=251.76$，$\sigma=\sqrt{251.76}≈15.87$，观测碰撞数282：
   $$Z = \frac{282-251.76}{15.87}≈1.90$$
   对应的单侧出现概率约2.87%，比第一个例子的概率高不少——这说明你之前假设的“概率大致等价”可能不准确，但也能看出，用Z分数就能直观对比两个样本的偏离程度。

更精确的概率计算 #

如果需要更精确的概率，可以分两种情况：

• 当$\mu$较小（比如$\mu<20$）：直接用泊松分布的概率质量函数计算：
  $$P(k) = e^{-\mu} \times \frac{\mu^k}{k!}$$
  可以用编程语言的数学库直接计算（比如Python的scipy.stats.poisson.pmf）。
• 当$\mu$较大（$\mu>20$）：用正态分布近似泊松分布（因为泊松分布会趋近于正态分布N(μ, μ)），计算观测值的累积分布函数（CDF）来得到出现该碰撞数及以上的概率。

设定异常阈值的步骤 #

1. 计算当前样本量n对应的理想碰撞数$\mu$
2. 计算标准差$\sigma=\sqrt{\mu}$
3. 选择合适的Z分数阈值（比如Z=2或Z=3）
4. 异常阈值的上限为$\mu + Z \times \sigma$，下限为$\max(0, \mu - Z \times \sigma)$（因为碰撞数不能为负）
5. 如果观测碰撞数超出这个范围，就可以判定为异常

备注：内容来源于stack exchange，提问作者bryc