Go 之 SortedMap 与 LinkedHashMap

前一段在关闭 IDEA 打开 GoLand 之后，深深感慨了一声

丝滑般享受

但没想到声音刚落，就发现又掉坑里了 /(ㄒoㄒ)/~~

{
    "foo": "Hello, World!",
    "bar": {
        "b": {
            "go": "1"
        },
        "a": {
            "go": "2"
        },
        "c": {
            "go": "3"
        }
    }
}

有如上一段 JSON，在程序中需要将其转为一个结构体以方便读取里边的数据，struct 的定义大概如下：

type Foobar struct {
    Foo  string `json:"foo"`
    Bar map[string]struct {
        Go string `json:"go"`
    } `json:"bar"`
}

现在有这么两个需求：

1. 按顺序输出 bar.a、bar.b、bar.c
2. 按顺序输出 bar.b、bar.a、bar.c

如果是用 Java 的小伙伴，肯定已经想到 SortedMap（用的比较多是 TreeMap）和 LinkedHashMap 了，前者是可以按 key 进行排序的，后者则可以保持键值对的插入顺序，而这两者都是 JDK 自带的，任何一个 Javaer 应该都使用过。

但是在 Go 语言的“简约设计”面前，这些都是不存在的——Go 只提供了最基础的 hash map。

并且，在借助 range 关键字对 Go 的 map 进行遍历访问的时候，会对 map 的 key 的顺序做随机化处理，也就是说即使是同一个 map 在同一个程序里进行两次相同的遍历，前后两轮访问 key 的顺序也是随机化的。(可以在这里验证：https://play.golang.org/p/s3Mj4gNfi4g )

在 Go 的官方 blog 的文章 Go maps in action 也确定了该现象确实存在，并且是有意而为之，

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 the release of Go 1.0, the runtime has randomized map iteration order.

那么在 Go 里边实现以上需求就得绕些路了。

实现类似 SortedMap 的遍历

SortedMap 主要是对 key 排序，那么我们便可将 map 的 key 全部拿出来，放到一个数组中，然后对这个数组排序后对有序数组遍历，再间接取 map 里的值就行了。

package main

import (
    "fmt"
    "sort"
)

func main() {
    m := make(map[string]string)
    m["b"] = "2"
    m["a"] = "1"
    m["c"] = "3"

    keys := make([]string, 0, len(m))
    for k, _ := range m {
        keys = append(keys, k)
    }

    sort.Strings(keys)

    for _, k := range keys {
        fmt.Printf("Key:%+v, Value:%+v\n", k, m[k])
    }
}

https://play.golang.org/p/vzpwizlRYUO

输出：

Key:a, Value:1
Key:b, Value:2
Key:c, Value:3

不过每次都要这么写有些麻烦，我们可以将其封装成一个方法

func sortedMap(m map[string]interface{}, f func(k string, v interface{})) {
    var keys []string
    for k := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    for _, k := range keys {
        f(k, m[k])
    }
}

然后这样调用

func main() {
    m := make(map[string]interface{})
    m["b"] = "2"
    m["a"] = "1"
    m["c"] = "3"

    sortedMap(m, func(k string, v interface{}) {
        val := v.(string)
        fmt.Printf("Key:%+v, Value:%+v\n", k, val)
    })
}

不过遗憾的是，因为 Go 不支持泛型，所以该方法并不是很通用（当 key 不为 string 的时候），但终究算是一个解决办法。

实现类似 LinkedHashMap

相比于上边按 key 排序来讲，在 Go 中实现 LinkedHashMap 要困难得多，要自己写一套数据结构。

之前有人试图给 Go 标准库提交过相关的代码，但是被拒绝了（(沮丧脸) 详情可见 7930: encoding/json: Optionally preserve the key order of JSON objects ），不过在 GitHub 上还是能找到相关的代码的：go-ordered-json，我们就可以用使用这个库来完成。

正如该项目的 ReadMe 中所说，你应该尽可能避免使用该库

If you can, you should avoid using this package.

但是对我来说，我没有更好的方案（第三方 API 返回的 JSON 中就是用 map 来保持顺序的），那么我也只好好好的 enjoy it 了。

package main

import (
    "fmt"
    "github.com/virtuald/go-ordered-json"
)

func main() {
    jsonString := `{
    "b": "2",
    "a": "1",
    "c": "3"
}`

    oo := json.OrderedObject{}
    err := json.Unmarshal([]byte(jsonString), &oo)
    if err != nil {
        panic(err)
    }
    fmt.Printf("%+v", oo)
}

输出结果：

[{Key:b Value:2} {Key:a Value:1} {Key:c Value:3}]

可以看出 json.OrderedObject 内部其实是把 map 处理成了 slice。

但是注意了：json.OrderedObject 只处理顶层的这个 map，如果嵌套有 map 的话，下层的 map 还是无序的。

（你可能会怀疑是不是因为用了 fmt.Printf 导致打印出来的顺序变了，你可以自己遍历试一下哦~）

现在来看看本文开头的那个 JSON 的例子

{
    "foo": "Hello, World!",
    "bar": {
        "b": {
            "go": "1"
        },
        "a": {
            "go": "2"
        },
        "c": {
            "go": "3"
        }
    }
}

如果我把上边代码中的 jsonString 换成上边的这个 JSON，那么输出的就会是

[{Key:foo Value:Hello, World!} {Key:bar Value:map[a:map[go:2] b:map[go:1] c:map[go:3]]}]

可以看出它只保证了最外层 foo 和 bar 的顺序， 而对于 bar 对应的这个 map，是按 a,b,c 的顺序来，并不是我们期望中的 b,a,c。

不过这个问题也是有解的，我们先创建一个 struct（和文章开头提到那个 struct 有点像），重点就是 Bar 的类型这里是 json.OrderedObject

type Foobar struct {
    Foo string             `json:"foo"`
    Bar json.OrderedObject `json:"bar"`
}

然后咱们来开始吧

package main

import (
    "fmt"
    "github.com/virtuald/go-ordered-json"
)

func main() {

    jsonString := `{
    "foo": "Hello, World!",
    "bar": {
        "b": {
            "go": "1"
        },
        "a": {
            "go": "2"
        },
        "c": {
            "go": "3"
        }
    }
}`

    foobar := Foobar{}
    err := json.Unmarshal([]byte(jsonString), &foobar)
    if err != nil {
        panic(err)
    }

    for _, value := range foobar.Bar {
        m := value.Value.(map[string]interface{})
        for k, v := range m {
            fmt.Printf("%+v.%+v=%+v\n", value.Key, k, v)
        }
    }

}

输出结果：

b.go=1
a.go=2
c.go=3

成功了是不是？！此处应该有掌声~

当然，是献给 virtuald/go-ordered-json 的~

encoding/json

有时间了可以研究一下 encoding/json 库，它的意义相对其他语言来说在 Go 中尤其重要——它还扮演着 struct 转换器的角色。

另外在用它对 map 进行 encode 的时候（就是 json.Marshal 咯），还是挺有意思的，大家猜猜下边这段代码，range 和 json 部分分别是什么样的结果？多运行几次呢？

package main

import (
    "encoding/json"
    "fmt"
)

func main() {
    jsonString := `{
    "foo": {
        "b": "1",
        "a": "2",
        "c": "3"
    }
}`
    o := make(map[string]map[string]string)
    err := json.Unmarshal([]byte(jsonString), &o)
    if err != nil {
        panic(err)
    }

    fmt.Println("range:")
    for _, m := range o {
        for k, v := range m {
            fmt.Printf("%s, %s\n", k, v)
        }
    }

    bytes, err := json.Marshal(o)
    if err != nil {
        panic(err)
    }

    fmt.Println("")
    fmt.Println("json:")
    fmt.Printf("%s\n", bytes)
}

有兴趣的朋友点击下边的 Go Playground 自己试试

https://play.golang.org/p/JcTWRlYjQ5j