Go:什么决定了映射键的迭代顺序? [英] Go: what determines the iteration order for map keys?

问题描述

Go 编程语言规范 说:

3.未指定映射的迭代顺序.[...]

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

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

That's to be expected since a map type can be implemented as a hash table, or as a search tree, or as some other data structure. But how is map actually implemented in Go?

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

Put differently, what determines the iteration order of the keys in

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

在我看到带有 string 键的地图显然 do 具有一定的迭代顺序后，我开始对此感到疑惑.类似的程序

I started wondering about this after I saw that a map with string keys apparently do have a certain iteration order. A program like

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()
}

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

prints the following on my machine:

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

无论插入顺序如何.

具有 map[byte]byte 映射的等效程序也以打乱顺序打印键，但这里的键顺序取决于插入顺序.

The equivalent program with a map[byte]byte map also prints the keys in a shuffled order, but here the key order depends on the insertion order.

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

How is all this implemented? Is the map specialized for integers and for strings?

推荐答案

Map 在 Go 中实现为 hashmap.

Map is implemented in Go as a hashmap.

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

The Go run-time uses a common hashmap implementation which is implemented in C. The only implementation differences between map[string]T and map[byte]T are: hash function, equivalence function and copy function.

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

Unlike (some) C++ maps, Go maps aren't fully specialized for integers and for strings.

在Go release.r60中，只要没有key冲突，迭代顺序就独立于插入顺序.如果存在冲突，则迭代顺序受插入顺序的影响.无论密钥类型如何，这都是正确的.string 类型的键和 byte 类型的键在这方面没有区别，因此您的程序总是以相同的顺序打印字符串键只是一个巧合.除非地图被修改，否则迭代顺序始终相同.

In Go release.r60, the iteration order is independent from insertion order as long as there are no key collisions. If there are collisions, iteration order is affected by insertion order. This holds true regardless of key type. There is no difference between keys of type string and keys of type byte in this respect, so it is only a coincidence that your program always printed the string keys in the same order. The iteration order is always the same unless the map is modified.

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

However, in the newest Go weekly release (and in Go1 which may be expected to be released this month), the iteration order is randomized (it starts at a pseudo-randomly chosen key, and the hashcode computation is seeded with a pseudo-random number). If you compile your program with the weekly release (and with Go1), the iteration order will be different each time you run your program. That said, running your program an infinite number of times probably wouldn't print all possible permutations of the key set. Example outputs:

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
...

这篇关于Go:什么决定了映射键的迭代顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！