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 := rangem {
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：
typeUser 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"}
foruserId, 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{
ifmapValue.Type().Kind() != reflect.Map {
return nil}
n := mapValue.Len()
key := make([]reflect.Value, 0, n)
value := make([]reflect.Value, 0, n)
iter := mapValue.MapRange()
foriter.Next() {
key = append(key, iter.Key())
value = append(value, iter.Value())
}
sorted := &SortedMap{
Key: key,
Value: value,
}
sort.Stable(sorted)
returnsorted
}
func compare(aVal, bVal reflect.Value) int{
aType, bType := aVal.Type(), bVal.Type()
ifaType != bType {
return -1 // No good answer possible, but dont return 0: theyre not equal.}
switchaVal.Kind() {
casereflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
a, b := aVal.Int(), bVal.Int()
switch{
casea < b:
return -1 casea > b:
return 1 default:
return 0}
casereflect.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