dictionary - map 迭代是否足够随机以随机选择键？

Question

我能否依靠 map 的随机迭代顺序在 Web 应用程序中实现客户端的随机“配对”？我试着环顾四周，但似乎无法找到这种随机性有多随机的细目。

算法看起来像这样:

var clients map[Client]struct{}

func PairClient(c Client) (Client, error) {
    for m := range clients {
        if m != c {
            return m, nil
        }
    }
    return nil, fmt.Errorf("lobby: insufficient number of clients")
}

当连接的客户端超过 1000 个时，这就足够了吗？还是我应该维护一个单独的客户端片段并从中随机选择？

Answer 1

尽管它说是随机的(随机化)(spec、blog、hashmap source、another blog、SO)，但分布远非完美。

为什么？因为我们喜欢快速的 map ，更好的随机分布往往需要更多的计算和/或更大的延迟。必须做出妥协。并且因为其目的不是通过 for range 提供高质量的“洗牌”功能，而只是为了防止开发人员依赖稳定的迭代顺序(因为即使没有显式随机化它也可能改变)。

但是这个分布“有多好”呢？容易得到“味道”。让我们创建一个 10 对的 map ，并开始对其进行多次迭代。让我们计算第一个索引(键)的分布:

m := map[int]int{}
for i := 0; i < 10; i++ {
    m[i] = i
}

dist := make([]int, 10)
for i := 0; i < 100000; i++ {
    for idx := range m {
        dist[idx]++
        break
    }
}

fmt.Println("Distribution:", dist)

输出(在 Go Playground 上尝试):

Distribution: [25194 24904 6196 6134 6313 6274 6297 6189 6189 6310]

前 2 个键(0 和 1)被遇到的概率比其余的大致相同4 倍。

你可以看出它是真实的(甚至是好的)随机性是非常糟糕的，但这不是重点。它足以提供不同的迭代顺序(而且重要的是:速度很快)。