likes
comments
collection
share

Go语言中常见100问题-#33 map迭代时陷阱与解决方法

作者站长头像
站长
· 阅读数 9

前言

大多数Gopher在处理map迭代时,因存在错误的假设,会产生惯性问题。本文主要讨论下面两种情况:

  • map迭代时顺序
  • 迭代时更新数据

map排序规则

golang中map有以下基础规则:

  • map数据不是按key排序的(因为golang中map不是基于二叉树实现的)

  • map中的数据顺序与向它里面添加数据时的顺序无关,例如,先向map中添加A后添加B, 并能保证map中数据A顺序在前B在后

map迭代时顺序不确定

当我们迭代map时,不能对里面的元素顺序做任何假定,下面分析这一原因。下图中的map含有4个bucket,每个bucket指向存储数据的地址。a、c、z、d、e、y分别表示元素的key.

Go语言中常见100问题-#33 map迭代时陷阱与解决方法

现在采用for range迭代上述map,打印key和value值。我们不要预期输出的结果为acdeyz(按key排序), 也不要预期是ayzcde(按插入排序)。

for k := range m {
    fmt.Print(k)
}

那是按存储的顺序aczdey输出吗?不!也不要有这种假设,在Go语言中,即使对同一个map迭代两次,输出的顺序也可能是不同的。下面运行两次上述程序的结果,可以看到,一次是zdyaec,另一次是czyade, 结果是不一样的。

NOTE:尽管map的迭代输出没有顺序保证,也不能说整体迭代结果是均匀分布的。在Go官方文档中说了map迭代的结果是不确定的,但不是随机的。

Go语言中的map迭代顺序为啥要设计成这样呢?这是语言设计者有意为之,他们想添加一些随机性在迭代的时候,使得开发人员在操作map时不要对输出顺序抱有期待(mng.bz/M2JW)。

特殊情况:标准库 encoding/json 在序列化map时按key排序

因此,作为一名Gopher,在迭代map时对输出顺序不要有任何预期。但是,在使用标准库或外部库时可能有些特别的地方。例如,在使用 encoding/json库将map对象序列化到json时,会按照key的字母顺序重新排序数据,不管插入map时数据顺序是什么样的,但这不是Go语言中map自生的特性。如果对顺序有强烈要求,我们应该使用基于二叉堆的数据结构(github.com/emirpasic/g…

下面这段代码将map对象序列化,然后输出序列化后的内容。运行结果可以看到,10次输出的内容都是一模一样的,都是按照key排序的,而不是插入顺序。

func main() {
    m := map[int]string{
        3: "ghi",
        1: "abc",
        2: "def",
    }

for i := 0; i < 10; i++ {
        byte, _ := json.Marshal(m)
        fmt.Println(string(byte))
    }
}

输出结果如下:

{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}
{"1":"abc","2":"def","3":"ghi"}

迭代map时更新数据

在Go语言中,在迭代的时候更新map(插入或删除数据)是允许的,不会产生编译错误和运行时错误。但是有一个点我们需要考虑,在迭代的时候向map中添加元素,需要避免不可预测性结果。

下面通过一个具体的例子说明,定义一个map[int]bool对象,遍历的时候如果value为true,添加一个新的元素到map中,猜猜这段代码输出结果是什么?

func main() {
    m := map[int]bool{
        0: true,
        1: false,
        2: true,
    }

    for k, v := range m {
        if v {
            m[k+10] = true
        }
    }

    fmt.Println(m)
}

实际结果:输出是不确定的,多次运行上述程序,得到的结果如下。

map[0:true 1:false 2:true 10:true 12:true 20:true 22:true 30:true]
map[0:true 1:false 2:true 10:true 12:true 20:true 22:true]
map[0:true 1:false 2:true 10:true 12:true]

为啥不具有唯一性呢?从官方文档中对map迭代时进行更新有这样的说明。

If a map entry is created during iteration, it may be produced during the iteration or skipped. The choice may vary for each entry created and from one iteration to the next.

因此,在迭代期间向map中添加元素,新增的元素可能在接下来的迭代中访问到,也可能访问不到。对于Gopher来说,没办法明确具体的行为。此外,从一轮迭代到另一个轮迭代,结果也可能不同。正如上述实验证实,多次执行程序,得到各种不同的结果。这一点需要牢记在心,如果想在迭代的时候更新元素,并且不对迭代有影响,可以采用下面的方法,在进行迭代前,对原始map做个拷贝,更新元素在新的map中进行。

func copyMap(m map[int]bool) map[int]bool {
    res := make(map[int]bool, len(m))
        for k, v := range m {
        res[k] = v
    }

    return res
}

func main() {
    m := map[int]bool{
        0: true,
        1: false,
        2: true,
    }

    m2 := copyMap(m)
    for k, v := range m {
        m2[k] = v
        if v {
            m2[10+k] = true
        }

    }

    fmt.Println(m2)
}

这段程序的输出具有唯一性,因为迭代是在m进行的,更新元素是在m2上,它们之间不会影响。

map[0:true 1:false 2:true 10:true 12:true]

思考总结

操作map对象时,我们需要注意以下几点:

  • map中数据是无序的,不是按key进行排序的

  • map中元素存储顺序不是按插入时先后顺序存储的

  • 遍历map输出的元素数据是无序的

  • 遍历map同时向里面新增元素,新增的元素不一定会被访问到

转载自:https://juejin.cn/post/7349068175899934754
评论
请登录