Go Map 加有序排序的一些掙扎
大家好，我是煎魚。
最近我有一個朋友又跟 map 扯上關系了，翻了個車。寫 Go 項目真的是和 map 藕斷絲連，時刻要注意。
今天看到社區內 map 加有序排序又各種掙扎過好幾輪。今天拋磚引玉。看看大家有沒有好的思路。
快速背景
Go 提供了一種內置的 map 類型，它實現了一個哈希表，在 Go 程序中普遍應用廣泛，能夠做一系列的增刪改查。
類型簽名如下：
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)
}
}輸出結果：
$ 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輸出結果看著沒有什么問題。但細心查看的同學應該發現了。在遍歷 map 類型時，訪問結果是無序的。明顯多執行幾次就會發現與我們聲明的順序不一致。
社區討論
這可不。這么尷尬的無序結果。對于初學者而言很容易導致潛在的 BUG，引發一些問題/事故。
大家為此做出過努力。提出過各種提案。例如：
- 《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]》
基于這些提案，也有人提出了新的關鍵字 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 兼容性保障規范：對 map 類型從無序改到有序，必然會存在破壞性變更。這活現在干不了。以后未來的 Go2 再說吧（拖字訣）。
- 排序后 map 的速度慢：如果將默認映射類型改為排序映射，那么不需要排序映射實現或已編寫代碼在需要時對鍵進行排序的人都會受到懲罰。（via @Dave Cheney）
- 實現穩定排序的 map 麻煩：Go 在標準庫 fmt 里實現了穩定排序的 map 輸出，整體實現較為難以解決。言外之意不建議將穩定排序加入 map 類型的支持內。（via @Rob Pike）
參考實現
Go 核心團隊推薦查看：https://github.com/golang/go/blob/master/src/internal/fmtsort/sort.go 的實現邏輯。如果要對 map 類型做穩定排序。要做一樣的事情，甚至更多。
說白了，就是要做大小對比、順序排序。還要適配所有的類型。
對應源代碼的其中一角：
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:
...
}如果只是標準庫 fmt 輸出流用到，常規的實現就行。但如果內置到 map 類型中，就還要考量性能、開銷、可維護性的綜合因素。折騰起來也是不太妙的，會引入不少的復雜度。
總結
雖然社區很多人提過很多種不同的建議。但，顯然，Go 核心團隊不是無法實現一個帶穩定排序的 map 類型。
為此在實現上要付出較高的改造代價和性能、開銷風險。外加 less is more 的設計哲學。導致此項功能特性一直停滯不前。
這個大背景下，大家也慢慢還是選擇了第三條路。使用第三方庫，或者配合 slice 來做，要不就是基于近年的泛型來實現了。
參考資料
[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
