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