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
是否专用于整数和字符串?
最佳答案
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
...
关于map - Go:什么决定了映射键的迭代顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9619479/