【GoLang笔记】遍历map时的key随机化问题及解决方法

之前的一篇笔记曾分析过，Go的map在底层是用hashmap实现的。由于高效的hash函数肯定不是对key做顺序散列的，所以，与其它语言实现的hashmap类似，在使用Go语言map过程中，key-value的插入顺序与遍历map时key的访问顺序是不相同的。熟悉hashmap的同学对这个情况应该非常清楚。
所以，本文要提到的肯定不是这个，而是一个比较让人惊奇的情况，下面开始说明。

1. 通过range遍历map时，key的顺序被随机化
在golang 1.4版本中，借助关键字range对Go语言的map做遍历访问时，前后两轮遍历访问到的key的顺序居然是被随机化的！
这个现象在其它语言中是很少见的，比如C语言实现hashmap时，通常会用数组（即一段连续的内存空间）来存key，虽然key的分布顺序与插入顺序不一致，但k-v数据填充完毕后，整个hashmap的key的次序是固定的，所以，后续遍历这个hashmap时，每轮遍历访问到的key的顺序是一致的。
但Go语言通过range遍历map时，确实会对map的key顺序做随机化。下面是一段简单的验证程序。

// map_range_rand.go
package main

import (
    "fmt"
)

func main() {
    m := make(map[string]string)
    m["hello"] = "echo hello"
    m["world"] = "echo world"
    m["go"] = "echo go"
    m["is"] = "echo is"
    m["cool"] = "echo cool"

    for k, v := range m {
        fmt.Printf("k=%v, v=%v\n", k, v)
    }
}

在go v1.4环境中，执行go build map_range_rand.go完成编译后，运行产出的2进制文件，结果如下。

第1次运行输出：

$ ./map_range_rand 
k=is, v=echo is
k=cool, v=echo cool
k=hello, v=echo hello
k=world, v=echo world
k=go, v=echo go

第2次运行输出：

$ ./map_range_rand 
k=go, v=echo go
k=is, v=echo is
k=cool, v=echo cool
k=hello, v=echo hello
k=world, v=echo world

第3次运行输出：

$ ./map_range_rand 
k=hello, v=echo hello
k=world, v=echo world
k=go, v=echo go
k=is, v=echo is
k=cool, v=echo cool

可以很清楚地看到，每次遍历时，key的顺序都是不同的。
后来在golang官方blog的文章Go maps in action中，确认了这个现象确实存在，而且是Go语言的设计者们有意为之，在这篇文章关于Iteration order的说明中提到：
When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation.
看起来是因为大家在使用Go的map时，可能会在业务逻辑中依赖map key的稳定遍历顺序，而Go底层实现并不保证这一点。因此，Go语言索性对key次序做随机化，以提醒大家不要依赖range遍历返回的key次序。
奇怪的是，我在golang 1.2环境中编译上面的示例代码后反复运行，输出结果中key的次序是非随机化的。
不过，不管如何，这个默认的次序肯定是不能依赖的。

2. 业务依赖key次序时，如何解决随机化问题

其实Go maps in action一文已经给出了解决方法：
If you require a stable iteration order you must maintain a separate data structure that specifies that order.
可见，需要另外维护一个数据结构来保持有序的key，然后根据有序key来遍历map。
下面是本文对上个例子给出的稳定遍历次序的解决方法。

package main

import (
	"fmt"
    "sort"
)

func main() {
    m := make(map[string]string)
    m["hello"] = "echo hello"
    m["world"] = "echo world"
    m["go"] = "echo go"
    m["is"] = "echo is"
    m["cool"] = "echo cool"

    sorted_keys := make([]string, 0)
    for k, _ := range m {
        sorted_keys = append(sorted_keys, k)
    }
  
    // sort 'string' key in increasing order
    sort.Strings(sorted_keys)

    for _, k := range sorted_keys {
        fmt.Printf("k=%v, v=%v\n", k, m[k])
    }		
}

上面的示例中，通过引入sort对key做排序，然后根据有序的keys遍历map即可保证每次遍历map时的key顺序是固定的。

$ go build map_range_rand.go 

可以验证，每次的执行结果中key的次序都是按字典序进行升序排列的：

$ ./map_range_rand
k=cool, v=echo cool
k=go, v=echo go
k=hello, v=echo hello
k=is, v=echo is
k=world, v=echo world

【参考资料】
Go Blog - Go maps in action

=========================== EOF ==========================

---