为什么Golang的MD5分布看起来不统一？

Question

我完全预料到我在某处有错误或误解了什么，但为什么以下代码似乎没有表现出均匀分布？

func TestMD5(t *testing.T) {
    n := 50000
    counts := map[uint32]int{} // # of hashes per 1/nth shard

    for i := 0; i < n; i++ {
        hash := md5.Sum(newUUID())
        result := binary.BigEndian.Uint32(hash[:4])
        counts[result/uint32(n)]++
    }

    dupeShards := 0
    dupeEntries := 0
    for _, count := range counts {
        if count > 1 {
            dupeShards++
            dupeEntries += count - 1
        }
    }
    t.Logf("%d inputs hashed to the same %d shards as other inputs.", dupeEntries, dupeShards)

    if len(counts) < n*95/100 {
        t.Fatalf("%d populated shards not within 5%% of expected %d uniform distribution!", len(counts), n)
    }
}

https://play.golang.org/p/05mA0Dl9GBG

—

代码说明：

MD5 50k 随机 UUID。
对于每个 MD5 和，取前 4 个字节并转换为 uint32。
将结果除以 50k（使用 truncated/floor 除法）以将哈希分布到 50k 均匀分布的分片中。

==> 我希望 50k MD5 总和均匀分布在 50k 分片上，但我一直看到只有 38k 分片填充，在 10k 分片中聚集：

main.go:29: 12075 inputs hashed to the same 9921 shards as other inputs.
main.go:32: 37925 populated shards not within 5% of expected 50000 uniform distribution!

我也可以用其他哈希值（例如 FNV）来复制它，所以我猜我误解了什么。感谢您的帮助！

Answer 1

这是绝对正常的行为，并未表明 MD5 实现存在任何偏差或错误。

您正在做的是（非常接近）取 50,000 个介于 0 和 49,999 之间的随机数。当您这样做时，几乎可以肯定许多数字会重复出现，因此有些数字不会出现。事实上，这 50,000 个数字完全不同且完全没有重复是不太可能的。

您可以用一个 six-sided 骰子来测试 - 如果您掷 6 次，您不太可能得到所有六个数字，更有可能看到其中的 3、4 或 5 个, 重复一次、两次或三次。它也与 so-called birthday paradox.

有关

这种现象的另一个例子是'Panini sticker question'。帕尼尼贴纸相册是一本书，里面有 space 约 600 张纪念世界杯足球赛的足球贴纸。每一个都有编号且不同，它们在数据包中随机呈现。您必须获得每个号码中的一个才能完成专辑。假设您购买了正确数量的贴纸来填满相册。如果你能完美地填满专辑，没有任何双打或遗漏贴纸，那将是非常幸运的。事实上，平均而言，您必须购买大量贴纸才能至少获得一张（如果您不与其他收藏家交换重复的贴纸）。

0-49,999 不同值出现的个数和显示'clumping'的个数可以用数学计算。我不确定你是如何测量结块的。但是从一次试验到下一次试验，38K 填充值的值将非常稳定，即使您看到的实际值会发生变化。

事实上，填充值的预期数量是 (1 - 1/e)n，其中 n 是可能值的数量，e 是数学常数 2.718281828... n=50000 的答案是31606。你当然不会总是得到这个值，但所有结果都应该在几百左右（在这里吐痰）。你在你的程序中犯了一个小错误，所以我无法破译给你 ~37000 的相关计算。

为什么Golang的MD5分布看起来不统一？

Why does Golang's MD5 distribution not appear to be uniform?

hash

md5

go