Go:什么决定了地图键的迭代顺序？

Question

在围棋编程语言规范说:

3.未指定地图上的迭代顺序.[...]

这是可以预料到的,因为地图类型可以实现为哈希表,搜索树或其他数据结构.但是如何map在Go中实际实现？

换句话说,决定键的迭代顺序的是什么

for k, _ := range m { fmt.Println(k) }

在我看到带string键的地图显然确实有一定的迭代顺序后,我开始对此感到好奇.像这样的程序

package main
import ("fmt"; "time"; "rand")

func main() {
    rand.Seed(time.Seconds())
    words := [...]string{"foo", "bar", "a", "b", "c", "hello", "world",
        "0", "1", "10", "100", "123"}
    stringMap := make(map[string]byte)
    for i := range rand.Perm(len(words)) {
        stringMap[words[i]] = byte(rand.Int())
    }
    fmt.Print("stringMap keys:")
    for k, _ := range stringMap { fmt.Print(" ", k) }
    fmt.Println()
}

在我的机器上打印以下内容:

stringMap keys: a c b 100 hello foo bar 10 world 123 1 0

无论插入顺序如何.

带有map[byte]byte映射的等效程序也以洗牌顺序打印密钥,但此处的密钥顺序取决于插入顺序.

这一切是如何实现的？是map专门为整数和字符串？

Answer 1

Map在Go中实现为hashmap.

Go运行时使用在C中实现的公共hashmap实现.map[string]T和之间唯一的实现差异map[byte]T是:哈希函数,等价函数和复制函数.

与(某些)C++映射不同,Go映射并不完全专用于整数和字符串.

在Go release.r60中,只要没有键冲突,迭代顺序就与插入顺序无关.如果存在冲突,则迭代顺序会受到插入顺序的影响.无论密钥类型如何,这都适用.在这方面,string类型的键和类型的键之间没有区别byte,因此程序始终以相同的顺序打印字符串键只是巧合.除非修改了地图,否则迭代顺序始终相同.

然而,在最新的Go每周版本中(以及可能预期在本月发布的Go1中),迭代顺序是随机的(它从伪随机选择的密钥开始,并且哈希码计算以伪随机方式播种)数).如果使用每周版本(以及使用Go1)编译程序,则每次运行程序时迭代顺序都会不同.也就是说,无限次地运行程序可能不会打印密钥集的所有可能的排列.示例输出:

stringMap keys: b 0 hello c world 10 1 123 bar foo 100 a
stringMap keys: hello world c 1 10 bar foo 123 100 a b 0
stringMap keys: bar foo 123 100 world c 1 10 b 0 hello a
...