【GoLang笔记】遍历map时的key随机化问题及解决方法

slvher · · 26238 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

之前的一篇笔记曾分析过,Go的map在底层是用hashmap实现的。由于高效的hash函数肯定不是对key做顺序散列的,所以,与其它语言实现的hashmap类似,在使用Go语言map过程中,key-value的插入顺序与遍历map时key的访问顺序是不相同的。熟悉hashmap的同学对这个情况应该非常清楚。
所以,本文要提到的肯定不是这个,而是一个比较让人惊奇的情况,下面开始说明。

1. 通过range遍历map时,key的顺序被随机化
在golang 1.4版本中,借助关键字range对Go语言的map做遍历访问时,前后两轮遍历访问到的key的顺序居然是被随机化的
这个现象在其它语言中是很少见的,比如C语言实现hashmap时,通常会用数组(即一段连续的内存空间)来存key,虽然key的分布顺序与插入顺序不一致,但k-v数据填充完毕后,整个hashmap的key的次序是固定的,所以,后续遍历这个hashmap时,每轮遍历访问到的key的顺序是一致的。
但Go语言通过range遍历map时,确实会对map的key顺序做随机化。下面是一段简单的验证程序。

// map_range_rand.go
package main

import (
    "fmt"
)

func main() {
    m := make(map[string]string)
    m["hello"] = "echo hello"
    m["world"] = "echo world"
    m["go"] = "echo go"
    m["is"] = "echo is"
    m["cool"] = "echo cool"

    for k, v := range m {
        fmt.Printf("k=%v, v=%v\n", k, v)
    }
}
在go v1.4环境中,执行go build map_range_rand.go完成编译后,运行产出的2进制文件,结果如下。

第1次运行输出:
$ ./map_range_rand 
k=is, v=echo is
k=cool, v=echo cool
k=hello, v=echo hello
k=world, v=echo world
k=go, v=echo go
第2次运行输出:
$ ./map_range_rand 
k=go, v=echo go
k=is, v=echo is
k=cool, v=echo cool
k=hello, v=echo hello
k=world, v=echo world
第3次运行输出:
$ ./map_range_rand 
k=hello, v=echo hello
k=world, v=echo world
k=go, v=echo go
k=is, v=echo is
k=cool, v=echo cool
可以很清楚地看到,每次遍历时,key的顺序都是不同的。
后来在golang官方blog的文章Go maps in action中,确认了这个现象确实存在,而且是Go语言的设计者们有意为之,在这篇文章关于Iteration order的说明中提到:
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 Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation.
看起来是因为大家在使用Go的map时,可能会在业务逻辑中依赖map key的稳定遍历顺序,而Go底层实现并不保证这一点。因此,Go语言索性对key次序做随机化,以提醒大家不要依赖range遍历返回的key次序。
奇怪的是,我在golang 1.2环境中编译上面的示例代码后反复运行,输出结果中key的次序是非随机化的。
不过,不管如何,这个默认的次序肯定是不能依赖的。

2. 业务依赖key次序时,如何解决随机化问题

其实Go maps in action一文已经给出了解决方法:
If you require a stable iteration order you must maintain a separate data structure that specifies that order.
可见,需要另外维护一个数据结构来保持有序的key,然后根据有序key来遍历map。
下面是本文对上个例子给出的稳定遍历次序的解决方法。
package main

import (
	"fmt"
    "sort"
)

func main() {
    m := make(map[string]string)
    m["hello"] = "echo hello"
    m["world"] = "echo world"
    m["go"] = "echo go"
    m["is"] = "echo is"
    m["cool"] = "echo cool"

    sorted_keys := make([]string, 0)
    for k, _ := range m {
        sorted_keys = append(sorted_keys, k)
    }
  
    // sort 'string' key in increasing order
    sort.Strings(sorted_keys)

    for _, k := range sorted_keys {
        fmt.Printf("k=%v, v=%v\n", k, m[k])
    }		
}
上面的示例中,通过引入sort对key做排序,然后根据有序的keys遍历map即可保证每次遍历map时的key顺序是固定的。
$ go build map_range_rand.go 
可以验证,每次的执行结果中key的次序都是按字典序进行升序排列的:
$ ./map_range_rand
k=cool, v=echo cool
k=go, v=echo go
k=hello, v=echo hello
k=is, v=echo is
k=world, v=echo world

【参考资料】
Go Blog - Go maps in action

=========================== EOF ==========================








有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:slvher

查看原文:【GoLang笔记】遍历map时的key随机化问题及解决方法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

26238 次点击  ∙  2 赞  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传