Go：什么决定地图键的迭代顺序？ [英] Go: what determines the iteration order for map keys?

问题描述

Go Programming Language Specification 说：

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

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

由于地图类型可以实现为哈希表或搜索树，或作为其他数据结构。但是在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?

换句话说，什么决定了密钥的迭代顺序， / p>

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

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

当我看到一张带有字符串键的地图显然是时，我开始怀疑具有一定的迭代顺序。程式如

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

<

regardless of the insertion order.

具有 map [byte] byte $ c> map也按顺序打印密钥，但这里的插入顺序上的密钥顺序依赖。

他执行了吗

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

推荐答案

地图是在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 ，只要不存在密钥冲突，迭代顺序与插入顺序无关。如果有冲突，则迭代顺序受到插入顺序的影响。无论密钥类型如何，都是这样。在这方面，键入 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屋！