映射迭代是否足够随机以随机选择密钥？

一尘不染

映射迭代是否足够随机以随机选择密钥？

我可以依靠地图的随机迭代顺序在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个时，这是否足够？还是应该维护一个单独的客户端片段并从中随机选择？

阅读 197

2020-07-02

共1个答案

一尘不染

尽管它说是随机的（随机的）（spec，blog，hashmap源，另一个blog，SO），但分布远非完美。

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

但是这种分布有多“好”呢？容易获得“味道”。让我们创建一个包含10对的地图，并开始对其进行多次迭代。让我们计算一下第一个索引（键）的分布：

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]

前两个键（0和1）碰到的几率大约是其余两个键的几倍，后者的几率大致相同。

您可以说这对于真正的（甚至是好的）随机性是很不好的，但这不是重点。它足以提供不同的迭代顺序（而且很重要：很快速）。

2020-07-02