Go Map 加有序排序的一些掙扎
大家好，我是煎魚。
最近我有一個朋友又跟 map 扯上關(guān)系了，翻了個車。寫 Go 項目真的是和 map 藕斷絲連，時刻要注意。
今天看到社區(qū)內(nèi) map 加有序排序又各種掙扎過好幾輪。今天拋磚引玉。看看大家有沒有好的思路。
快速背景
Go 提供了一種內(nèi)置的 map 類型，它實現(xiàn)了一個哈希表，在 Go 程序中普遍應(yīng)用廣泛，能夠做一系列的增刪改查。
類型簽名如下：
map[KeyType]ValueType最小演示代碼：
func main() {
m := make(map[int32]string)
m[0] = "煎魚1"
m[1] = "煎魚2"
m[2] = "煎魚3"
m[3] = "煎魚4"
m[4] = "煎魚5"
m[5] = "煎魚6"
for k, v := range m {
log.Printf("k: %v, v: %v", k, v)
}
}輸出結(jié)果：
$ go run demo.go
2023/12/28 23:36:02 k: 2, v: 煎魚3
2023/12/28 23:36:02 k: 3, v: 煎魚4
2023/12/28 23:36:02 k: 4, v: 煎魚5
2023/12/28 23:36:02 k: 5, v: 煎魚6
2023/12/28 23:36:02 k: 0, v: 煎魚1
2023/12/28 23:36:02 k: 1, v: 煎魚2輸出結(jié)果看著沒有什么問題。但細(xì)心查看的同學(xué)應(yīng)該發(fā)現(xiàn)了。在遍歷 map 類型時，訪問結(jié)果是無序的。明顯多執(zhí)行幾次就會發(fā)現(xiàn)與我們聲明的順序不一致。
社區(qū)討論
這可不。這么尷尬的無序結(jié)果。對于初學(xué)者而言很容易導(dǎo)致潛在的 BUG，引發(fā)一些問題/事故。
大家為此做出過努力。提出過各種提案。例如：
- 《proposal: Go 2: add native type for map that maintains key order[1]》
- 《proposal: add string key sorted map as built in type[2]》
- 《proposal: Add a sorting function for map[3]》
基于這些提案，也有人提出了新的關(guān)鍵字 sortedMap：
type User struct{
UserId string
Name string
}
func main(){
db := sortedMap[string]*User{}
db["煎魚2"] = &User{UserId:"煎魚2",Name:"n2"}
db["煎魚1"] = &User{UserId:"煎魚1",Name:"n1"}
for userId, user := range db {
fmt.Println(userId, user.Name)
}
// should output
// 煎魚1 n1
// 煎魚2 n2
}但最終都失敗告終。原因不外乎以下幾類原因：
- Go1 兼容性保障規(guī)范：對 map 類型從無序改到有序，必然會存在破壞性變更。這活現(xiàn)在干不了。以后未來的 Go2 再說吧（拖字訣）。
- 排序后 map 的速度慢：如果將默認(rèn)映射類型改為排序映射，那么不需要排序映射實現(xiàn)或已編寫代碼在需要時對鍵進(jìn)行排序的人都會受到懲罰。（via @Dave Cheney）
- 實現(xiàn)穩(wěn)定排序的 map 麻煩：Go 在標(biāo)準(zhǔn)庫 fmt 里實現(xiàn)了穩(wěn)定排序的 map 輸出，整體實現(xiàn)較為難以解決。言外之意不建議將穩(wěn)定排序加入 map 類型的支持內(nèi)。（via @Rob Pike）
參考實現(xiàn)
Go 核心團(tuán)隊推薦查看：https://github.com/golang/go/blob/master/src/internal/fmtsort/sort.go 的實現(xiàn)邏輯。如果要對 map 類型做穩(wěn)定排序。要做一樣的事情，甚至更多。
說白了，就是要做大小對比、順序排序。還要適配所有的類型。
對應(yīng)源代碼的其中一角：
type SortedMap struct {
Key []reflect.Value
Value []reflect.Value
}
func (o *SortedMap) Len() int { return len(o.Key) }
func (o *SortedMap) Less(i, j int) bool { return compare(o.Key[i], o.Key[j]) < 0 }
func (o *SortedMap) Swap(i, j int) {
o.Key[i], o.Key[j] = o.Key[j], o.Key[i]
o.Value[i], o.Value[j] = o.Value[j], o.Value[i]
}
func Sort(mapValue reflect.Value) *SortedMap {
if mapValue.Type().Kind() != reflect.Map {
return nil
}
n := mapValue.Len()
key := make([]reflect.Value, 0, n)
value := make([]reflect.Value, 0, n)
iter := mapValue.MapRange()
for iter.Next() {
key = append(key, iter.Key())
value = append(value, iter.Value())
}
sorted := &SortedMap{
Key: key,
Value: value,
}
sort.Stable(sorted)
return sorted
}
func compare(aVal, bVal reflect.Value) int {
aType, bType := aVal.Type(), bVal.Type()
if aType != bType {
return -1 // No good answer possible, but don't return 0: they're not equal.
}
switch aVal.Kind() {
case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
a, b := aVal.Int(), bVal.Int()
switch {
case a < b:
return -1
case a > b:
return 1
default:
return 0
}
case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
...
}如果只是標(biāo)準(zhǔn)庫 fmt 輸出流用到，常規(guī)的實現(xiàn)就行。但如果內(nèi)置到 map 類型中，就還要考量性能、開銷、可維護(hù)性的綜合因素。折騰起來也是不太妙的，會引入不少的復(fù)雜度。
總結(jié)
雖然社區(qū)很多人提過很多種不同的建議。但，顯然，Go 核心團(tuán)隊不是無法實現(xiàn)一個帶穩(wěn)定排序的 map 類型。
為此在實現(xiàn)上要付出較高的改造代價和性能、開銷風(fēng)險。外加 less is more 的設(shè)計哲學(xué)。導(dǎo)致此項功能特性一直停滯不前。
這個大背景下，大家也慢慢還是選擇了第三條路。使用第三方庫，或者配合 slice 來做，要不就是基于近年的泛型來實現(xiàn)了。
參考資料
[1]proposal: Go 2: add native type for map that maintains key order: https://github.com/golang/go/issues/41289
[2]proposal: add string key sorted map as built in type: https://github.com/golang/go/issues/22865
[3]proposal: Add a sorting function for map: https://github.com/golang/go/issues/39291
