地图迭代是否足够随机选择密钥？

Question

我可以依赖地图的随机迭代顺序来实现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

即使它被称为随机(随机)(规范,博客,哈希地图源,另一个博客,SO),分布远非完美.

为什么？因为我们喜欢地图快速,更好的随机分布往往需要更多的计算和/或更大的延迟.必须妥协.并且因为其目的不是为了提供高质量的"shuffle"功能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)大致比其他两个键(和大概相同的概率)多4倍.

你可以说它是真实的(甚至是好的)随机的非常糟糕,但这不是重点.它足以提供不同的迭代顺序(重要的是:它很快).

Answer 2

从规格来看：

3. 映射的迭代顺序未指定，并且不保证从一次迭代到下一次迭代的顺序相同。（...）

这本质上意味着映射的迭代顺序是未定义的。即使现在默认的 Go 编译器是随机的，其他编译器或其他版本也可能会有所不同。