开始：什么决定了地图键的迭代顺序？

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中作为哈希图实现。

Go运行时使用通用的hashmap实现，该实现在C中实现。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
...