map - Go:什么决定了映射键的迭代顺序？

Question

Go Programming Language Specification说:

3. The iteration order over maps is not specified. [...]

这是意料之中的，因为映射类型可以实现为哈希表、搜索树或其他一些数据结构。但是 map 实际上是如何在 Go 中实现的呢？

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

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

在我看到带有 string 键的 map 显然 确实 具有特定的迭代顺序后，我开始对此感到疑惑。像这样的程序

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 映射的等效程序也以打乱顺序打印键，但此处的键顺序取决于插入顺序。 p>

这一切是如何实现的？ map 是否专用于整数和字符串？

Answer 1

Map 在 Go 中作为 hashmap 实现。

Go 运行时使用在 C 中实现的通用 hashmap 实现。map[string]T 和 map[byte]T 之间的唯一实现差异是: 散列函数、等价函数和复制函数。

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

在 Go release.r60 中，迭代顺序与插入顺序无关，只要不存在键冲突即可。如果存在冲突，迭代顺序会受到插入顺序的影响。无论 key 类型如何，这都适用。 string 类型的键和 byte 类型的键在这方面没有区别，所以你的程序总是以相同的顺序打印字符串键只是巧合.除非修改 map ，否则迭代顺序始终相同。

然而，在最新的 Go 每周发布(以及可能预计在本月发布的 Go1 中)，迭代顺序是随机的(它从伪随机选择的 key ，哈希码计算以伪随机数为种子)。如果你用每周发布的版本(和 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
...