go - 为什么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(使用截断/底除法)以将哈希分布到 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 个数字完全不同且完全没有重复是不太可能的。

你可以用一个六面骰子来测试这个——如果你掷 6 次，你不太可能得到所有六个数字，更有可能看到大约 3、4 或 5 个，其中一个，重复两到三次。它也与所谓的birthday paradox有关。 .

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

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

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