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
  default:
   return 0
  }
 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:

  ...

}