本文将简单讲解一下map的常见使用,会把主要的流程描述一下,具体细节不会过多阐述(因为我也没看全,需要遇到问题时再仔细看源码)。我用Go时间还不长,还在学习阶段,如果有误,欢迎批评指正,感谢~
1 哈希计算与碰撞
1.1 哈希计算
map在各个语言中,都是很常见的。其底层运用的就是hash。在Go中也不例外。
hash 计算就是根据key经过hash计算,找到其存储的位置,然后将对应的值存放在这个位置。
1.2 碰撞
通常,讲到hash 计算,就不可避免地讲到hash碰撞。什么意思呢? 就是两个不同的key经过hash计算,找到的位置是一样的。
那么怎么解决呢?
有如下两种方案:
(1)开放寻址法: 即如果keyA经过计算,找到了位置A,发现位置A上有元素了,就会一直往后找,知道找到一个空位置。
(2)拉链法:如果两个key计算之后,位置相同,那么就会针对这个位置建立一个链表,从前往后插入这个位置上的多个key. Go语言中采用的就是这种方案。
2 map的内存分配
先上个图:
[图片来源:https://mp.weixin.qq.com/s/2CDpE5wfoiNXm1agMAq4wA]
解释一下:
- 每个map都有一个hmap, 这个结构里面的几个字段重点讲一下:
count 表示map中元素的数量,在使用len时,就是使用的这个字段。
B 表示桶数量的位数,当前map bucket的数量为 2^B 个。
buckets : 桶,每个桶代表了一个bmap 数组。
oldbuckets: 在map 扩容时,会将bucket 指向oldbuckets.
extra 表示预先分配的桶。
- bmap 具体存放k-v的地方。
大体是这个样子的:
HOB Hash : 第一行 红色的部分,表示当前桶中的第几个cell 。
keys: 接下来是存储key的地方
value: 黄色部分是value部分
最后是overflow, 表示如果hash到当前的key过多时,需要生成新的 bmap,用来存放更多的k-v 。
3 一般操作(无扩容场景)
在讲解操作之前,我们先看下一个具体的key 是怎么存储的。
其实如果不考虑扩容,map的操作是很简单的。本小节的内容都不考虑扩容。
3.1 存储/更新
(不考虑扩容)具体的步骤如下:
(1) 先对keyA进行hash
(2) 根据B获取后几位,图中例子是5. 取后五位,找到对应的桶。后五位为00110, 所以也正好位于bucket 5 中。
(3) 根据前8位 找到桶中的第几个cell【也就是top信息】.
(4)遍历桶的每个cell, 首先看top信息是否跟 keyA 的top一直,如果top不一致,直接进行下一个cell ;如果top 一致,且当前cell 为空,则直接存储; 如果top一致,cell位置上有key,且与keyA相等,则此时更新; 如果top 一致,cell 位置上有key, 但与keyA不是同一个,则需要去申请overflow 中分配,overflow 也满了,则一致申请overflow 。。。
3.2 查询
查询步骤跟存储差不多。
步骤:
(1) 根据keyA取hash,找到对应的桶跟cell.
(2) 遍历桶中的元素,比较cell 中key与keyA的 top、key是否都一致;如果二者都一致,则返回; 如果二者有任何一个不一致,则看是否有overflow, 如果有继续遍历;没有overflow ,则返回对应元素类型的零值,结束流程。
3.3 删除 【可以看下这个函数 mapdelete】
步骤:
(1) 根据keyA取hash,找到对应的桶跟cell.
(2) 遍历桶中的元素,比较cell 中key与keyA的 top、key是否都一致;如果二者都一致,则删除,结束流程; 如果二者有任何一个不一致,则看是否有overflow, 如果有继续遍历overflow 的bmap;没有overflow ,则返回对应元素类型的零值,结束流程。
4 扩容
4.1 为什么要扩容?
1、已经到了 load factor 的临界点: 了解了查询的过程,我们发现,当大多数桶中元素太多,导致桶快满时,map的性能会急剧下降。此时需要扩容。
2、 overflow 的桶: 另外,我们发现,如果桶存在太多的overflow 的桶 ,此时要逐个overflow去遍历,此时性能也会下降。
4.2 扩容的方式
- 针对 1,将 B + 1,进而 hmap 的 bucket 数组扩容一倍;biggerSizeGrow
假设旧桶数组大小为2^B, 新桶数组大小为2*2^B,对于某个hash值X
若 X & (2^B) == 0,说明 X < 2^B,那么它将落入与旧桶集合相同的索引xi中;
否则,它将落入xi + 2^B中。
例如,对于旧B = 3时,hash1 = 4,hash2 = 20,其搬迁结果类似这样。
- 针对 2,通过移动 bucket 内容,使其倾向于紧密排列从而提高 bucket 利用率。 sameSizeGrow,即是不改变大小的扩容动作。
4.3 扩容的迁移过程
扩容最核心的就是迁移过程。迁移过程中也区分了上述两个情况。
看一个网上的图片,画的很棒:
图片来自 https://www.jianshu.com/p/aa0d4808cbb8
5 扩容下操作的注意事项
在第三节,我们分析了不包含扩容的几个基本操作,如果包含了扩容,那么这几个操作需要关注什么呢?
5.1 扩容下的存储
如果正在扩容,那么每次设置、修改hash值时,都会触发growWork,对哈希表的内容进行增量拷贝。
5.2 扩容下的查询
oldbucket 存在且未被迁移,则需要使用old bucket中的数据。
5.3 扩容下的删除
如果删除过程中发生扩容,就会对即将发生操作的桶进行分流,随后找到桶中的目标元素,完成键值对的删除。
6 遍历与传参的注意事项
6.1 for range遍历
for range 遍历时,k, v 是先拷贝一份的,如果对v 进行操作,是不会影响原map的数据的。
来个例子:
func TestForRange(t *testing.T) {
maps1 := map[string]int {
"frank" : 1,
"chris" : 2,
}
fmt.Println("更新v, 对原数组无影响============")
for _,v := range maps1 {
v++
}
for k,v := range maps1 {
fmt.Println(k, v)
}
fmt.Println("要想使更新生效, 需要这样做============")
for k,v := range maps1 {
maps1[k] = v + 1
}
for k,v := range maps1 {
fmt.Println(k, v)
}
结论:
更新v, 对原数组无影响============
frank 1
chris 2
要想使更新生效, 需要这样做============
frank 2
chris 3
6.2 传参
虽然Go中传参时,使用的值传递,但是我们知道map的定义时,会生成一个指针。所以即使是传了map自身给另外一个函数,其底层仍然传的的是map的指针。所以在函数中更新map的值,也会对原来的map产生影响。这个slice不同,slice如果使用自身,其是它传的结构体,所以在函数中改变slice, 不会影响原来的slice。
func operationOfMapWithValueparam(mapTest map[string]float32, sliceTest []int) {
mapTest["lmm"] = 11
sliceTest = append(sliceTest, 3)
}
func TestMapAsParam(t *testing.T) {
mapTest := make(map[string]float32)
mapTest["frank"] = 1
mapTest["chris"] = 2
sliceTest := []int{1,2}
fmt.Println("before param -- map: ", mapTest, " slice: ", sliceTest)
operationOfMapWithValueparam(mapTest, sliceTest)
fmt.Println("after param -- map: ", mapTest, " slice: ", sliceTest)
}
结论是
before param -- map: map[frank:1 chris:2] slice: [1 2]
after param -- map: map[frank:1 chris:2 lmm:11] slice: [1 2]
7 总结
本文先讲解了常见语言map使用的hash, 及其碰撞。接下来降级了Go语言中map的结构。第三部分在屏蔽扩容场景的情况下,讲解了增删改查的操作。第四部分则简单讲解了扩容相关的知识。最后通过demo 罗列了对for range 以及传参的情况下的注意事项。
8 参考文献
map底层实现,很多很赞的流程图 https://www.jianshu.com/p/aa0d4808cbb8
深度解密Go语言之map https://mp.weixin.qq.com/s/2CDpE5wfoiNXm1agMAq4wA
哈希表 https://draveness.me/golang/datastructure/golang-hashmap.html
map https://github.com/cch123/golang-notes/blob/master/map.md
9 其他
本文是《循序渐进go语言》的第九篇-《Go-map》。
如果有疑问,可以直接留言,也可以关注公众号 “链人成长chainerup” 提问留言,或者加入知识星球“链人成长” 与我深度链接~