Tony Bai · Go 语言第一课
Tony Bai
资深架构师,tonybai.com 博主
20432 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 59 讲
开篇词 (1讲)
结束语 (1讲)
Tony Bai · Go 语言第一课
15
15
1.0x
00:00/00:00
登录|注册

16|复合数据类型:原生map类型的实现机制是怎样的?

你好,我是 Tony Bai。
上一节课,我们学习了 Go 语言中最常用的两个复合类型:数组与切片。它们代表一组连续存储的同构类型元素集合。不同的是,数组的长度是确定的,而切片,我们可以理解为一种“动态数组”,它的长度在运行时是可变的。
这一节课,我们会继续前面的脉络,学习另外一种日常 Go 编码中比较常用的复合类型,这种类型可以让你将一个值(Value)唯一关联到一个特定的键(Key)上,可以用于实现特定键值的快速查找与更新,这个复合数据类型就是 map。很多中文 Go 编程语言类技术书籍都会将它翻译为映射、哈希表或字典,但在我的课程中,为了保持原汁原味,我就直接使用它的英文名,map
map 是我们继切片之后,学到的第二个由 Go 编译器与运行时联合实现的复合数据类型,它有着复杂的内部实现,但却提供了十分简单友好的开发者使用接口。这一节课,我将从 map 类型的定义,到它的使用,再到 map 内部实现机制,由浅到深地让你吃透 map 类型。

什么是 map 类型?

map 是 Go 语言提供的一种抽象数据类型,它表示一组无序的键值对。在后面的讲解中,我们会直接使用 key 和 value 分别代表 map 的键和值。而且,map 集合中每个 key 都是唯一的:
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Tony Bai · Go 语言第一课》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(62)

  • 最新
  • 精选
  • 用0和1改变自己
    可以用一个有序结构存储key,如slice,然后for这个slice,用key获取值。资料来源至:https://go.dev/blog/maps

    作者回复: ✅

    3
    32
  • ddh
    请问一下老师, map 元素不能寻址, 是因为动态扩容, 那么切片不也有动态扩容吗。 为什么切片元素可以寻址呢? 难道切片动态扩容之后, 它的元素地址不会变吗

    作者回复: 好问题! 关于这个问题,官方没有明确说明。 我觉得之所以map element是不可寻址的,还是复杂性和安全性的考虑。 Go slice和map都是复合数据类型,但两者的内部实现复杂度却远远不同。map要远复杂于slice。 slice的元素的地址要么在要么在原底层数组中,要么在扩容后的新数组中。并且slice扩容是一次完成的。 但map扩容是“蚂蚁搬家”,element位置复杂一些,可能在原bucket中、可能在overflow bucket中,也可能在新扩容的bucket中。 此外,一旦暴露map element的地址,比如我们用一个栈上的指针变量引用了该地址,当发生element移动时,go就要考虑连带变更这些栈上指针变量的指向,这些变更操作在每个map操作中都会导致运行时消耗的增加。 至于安全性,map有着一个复杂内部结构,这个结构环环相扣。一旦map element地址被暴露,通过该地址不仅可以修改value值,还可能会对map内部结构造成破坏,这种破坏将导致整个map工作不正常。而slice的element即便被hack,改掉的也只是元素值。

    3
    17
  • thomas
    go团队为什么要故意把map的遍历设置为随机?

    作者回复: 这一话题要追溯到Go 1.0版本发布的时候,从Go 1.0版本的发布文档- https://go.dev/doc/go1中,我们能找到如下内容: The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another. In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order. This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map. 翻译过来,大致意思就是:1.0版本之前的语言规范中没有规定map的迭代次序,从而导致在实践中的一些糟糕的开发运行体验。于是Go团队选 择故意在map中加入随机迭代功能,这样一旦出现开发人员依赖key迭代顺序的错误行为,这一行为导致的问题在开发和测试早期就能被及时发现,而不会出现在生产运行环境中导致更大的危害。

    15
  • Geek_244c46
    map的key和value的值,是否可以为null

    作者回复: 用代码回答你的问题:) // testnilasmapkey.go package main func main() { var m = make(map[*int]*int) m[nil] = nil println(m) println(len(m)) var b = 5 m[nil] = &b p := m[nil] println(*p) } 0xc0000466b0 1 5 nil作为value不新鲜。但nil可作为key可是很多人都不知道的。

    11
  • 不负青春不负己🤘
    可以把key 赋值到变量,使用sort 排序,在遍历

    作者回复: ✅

    6
  • flexiver
    老师,想请问一下,hmap这个结构中的extra字段, 在key和value都不是指针的情况下,会存储所有的overflow bucket的指针,里面有提到一个内联,这个内联是什么意思?以及为什么当key和value都不是指针的情况下,会将bucket中的overflow指针全部放到extra字段存储

    作者回复: 在Go项目源码(Go 1.17版本)的 src/cmd/compile/internal/reflectdata/reflect.go中,func MapBucketType(t *types.Type) *types.Type>这个函数实现中,我们可以勾勒出一个bucket桶的结构: tophash keys values overflow pointer 不过这个overflow pointer有两种情况: // If keys and elems have no pointers, the map implementation // can keep a list of overflow pointers on the side so that // buckets can be marked as having no pointers. // Arrange for the bucket to have no pointers by changing // the type of the overflow field to uintptr in this case. // See comment on hmap.overflow in runtime/map.go. otyp := types.Types[types.TUNSAFEPTR] if !elemtype.HasPointers() && !keytype.HasPointers() { otyp = types.Types[types.TUINTPTR] } 当key和value中都没有指针时,比如map[int]int。此时考虑到gc优化,编译器将overflow的类型设置为uintptr。 uintptr是一个整型,无法被GC识别,这样一来uintptr指向的overflow bucket就没有指向它的指针,这样gc就会将overflow bucket视为unrea chable的mem块而将其释放掉。为了避免这种情况,hmap中的extra此时就会指向上面这类bucket的overflow bucket,保证key和value中都不含指针时,overflow bucket依旧可以不被gc。

    5
  • 文经
    我看了《Go语言实践》,《Go专家编程》,《Go语言底层原理剖析》这几本书对map的描述,对比才发现白老师讲得最清晰,在封装和细节方面拿捏得最好,大大地赞👍 剩下不清楚的地方就只能自己看源码了。

    作者回复: 过奖。其实原理这东西最终还是要落到代码上。而且不同版本实现也有差异。要想真正把原理吃透,还得自己多过几遍代码

    4
  • ddh
    把key存到有序切片中,用切片遍历

    作者回复: 是一个可行方法。

    2
    4
  • Unknown element
    老师我想问下这里: “如果是因为 overflow bucket 过多导致的“扩容”,实际上运行时会新建一个和现有规模一样的 bucket 数组,然后在 assign 和 delete 时做排空和迁移。” 如果bucket规模不变的话,那所有key在hash之后还是分到原来的桶中,好像该overflow还是会overflow?主要是因为这里既没有通过真正增加桶的数量实现扩容,也没有通过更换hash函数改变key在桶中的分布,那么这个overflow的问题到底是怎么解决的呢?谢谢老师

    作者回复: 好问题。这个等量扩容来自这个issue:https://github.com/golang/go/issues/16070 这是一种比较特殊的情况,即当持续向哈希中插入数据,然后又将它们全部删除时,这个过程如果触发增容扩容,就会导致overflow bucket过多,但此时原bucket中已经没有数据了。所以go引入了利用现有扩容机制的等量扩容 https://github.com/golang/go/commit/9980b70cb460f27907a003674ab1b9bea24a847c 将原bucket的overflow bucket中的数据重新挪到新bucket中。算法较复杂,专栏定位入门,所以没进行深入。感兴趣可以读一下这个cl commit的源码。

    归属地:北京
    3
  • Tokamak
    老师,请问一下如果是因为overflow bucket过多导致的"扩容", 是否可以理解为这个hash函数的算法不太合理,导致大部分的key都分配到了一个bucket中,是否可以通过修改hash算法来重新hash一遍呢?

    作者回复: go map底层的hash函数要考虑通用性。谁也不能预测用户会使用什么样的key数据。

    3
收起评论
显示
设置
留言
62
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部