http://studygolang.com/articles/2749
之前的一篇筆記曾分析過，Go的map在底層是用hashmap實(shí)現(xiàn)的。由于高效的hash函數(shù)肯定不是對key做順序散列的，所以，與其它語言實(shí)現(xiàn)的hashmap類似，在使用Go語言map過程中，key-value的插入順序與遍歷map時(shí)key的訪問順序是不相同的。熟悉hashmap的同學(xué)對這個(gè)情況應(yīng)該非常清楚。
所以，本文要提到的肯定不是這個(gè)，而是一個(gè)比較讓人驚奇的情況，下面開始說明。
1. 通過range遍歷map時(shí)，key的順序被隨機(jī)化
在golang 1.4版本中，借助關(guān)鍵字range對Go語言的map做遍歷訪問時(shí)，前后兩輪遍歷訪問到的key的順序居然是被隨機(jī)化的！
這個(gè)現(xiàn)象在其它語言中是很少見的，比如C語言實(shí)現(xiàn)hashmap時(shí)，通常會用數(shù)組（即一段連續(xù)的內(nèi)存空間）來存key，雖然key的分布順序與插入順序不一致，但k-v數(shù)據(jù)填充完畢后，整個(gè)hashmap的key的次序是固定的，所以，后續(xù)遍歷這個(gè)hashmap時(shí)，每輪遍歷訪問到的key的順序是一致的。
但Go語言通過range遍歷map時(shí)，確實(shí)會對map的key順序做隨機(jī)化。下面是一段簡單的驗(yàn)證程序。
// 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環(huán)境中，執(zhí)行g(shù)o build map_range_rand.go完成編譯后，運(yùn)行產(chǎn)出的2進(jìn)制文件，結(jié)果如下。
第1次運(yùn)行輸出：
$ ./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次運(yùn)行輸出：$ ./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次運(yùn)行輸出：$ ./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
可以很清楚地看到，每次遍歷時(shí)，key的順序都是不同的。后來在golang官方blog的文章Go maps in action中，確認(rèn)了這個(gè)現(xiàn)象確實(shí)存在，而且是Go語言的設(shè)計(jì)者們有意為之，在這篇文章關(guān)于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.看起來是因?yàn)榇蠹以谑褂肎o的map時(shí)，可能會在業(yè)務(wù)邏輯中依賴map key的穩(wěn)定遍歷順序，而Go底層實(shí)現(xiàn)并不保證這一點(diǎn)。因此，Go語言索性對key次序做隨機(jī)化，以提醒大家不要依賴range遍歷返回的key次序。奇怪的是，我在golang 1.2環(huán)境中編譯上面的示例代碼后反復(fù)運(yùn)行，輸出結(jié)果中key的次序是非隨機(jī)化的。不過，不管如何，這個(gè)默認(rèn)的次序肯定是不能依賴的。
2. 業(yè)務(wù)依賴key次序時(shí)，如何解決隨機(jī)化問題
其實(shí)Go maps in action一文已經(jīng)給出了解決方法：
If you require a stable iteration order you must maintain a separate data structure that specifies that order.
可見，需要另外維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)來保持有序的key，然后根據(jù)有序key來遍歷map。
下面是本文對上個(gè)例子給出的穩(wěn)定遍歷次序的解決方法。
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做排序，然后根據(jù)有序的keys遍歷map即可保證每次遍歷map時(shí)的key順序是固定的。$ go build map_range_rand.go
可以驗(yàn)證，每次的執(zhí)行結(jié)果中key的次序都是按字典序進(jìn)行升序排列的：$ ./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
posted on 2017-02-05 11:32
思月行云 閱讀(291)
評論(0) 編輯 收藏 引用 所屬分類:
Golang