Go-map

本文将简单讲解一下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的内存分配

先上个图:

map.png

[图片来源: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的地方。
    大体是这个样子的:
bmap.png

HOB Hash : 第一行 红色的部分,表示当前桶中的第几个cell 。
keys: 接下来是存储key的地方
value: 黄色部分是value部分
最后是overflow, 表示如果hash到当前的key过多时,需要生成新的 bmap,用来存放更多的k-v 。

3 一般操作(无扩容场景)

在讲解操作之前,我们先看下一个具体的key 是怎么存储的。


key-bucket-cell.png

其实如果不考虑扩容,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 。。。

insert-update.png

3.2 查询

查询步骤跟存储差不多。
步骤:

(1) 根据keyA取hash,找到对应的桶跟cell.
(2) 遍历桶中的元素,比较cell 中key与keyA的 top、key是否都一致;如果二者都一致,则返回; 如果二者有任何一个不一致,则看是否有overflow, 如果有继续遍历;没有overflow ,则返回对应元素类型的零值,结束流程。

select.png

3.3 删除 【可以看下这个函数 mapdelete】

步骤:

(1) 根据keyA取hash,找到对应的桶跟cell.
(2) 遍历桶中的元素,比较cell 中key与keyA的 top、key是否都一致;如果二者都一致,则删除,结束流程; 如果二者有任何一个不一致,则看是否有overflow, 如果有继续遍历overflow 的bmap;没有overflow ,则返回对应元素类型的零值,结束流程。

delete.png

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,其搬迁结果类似这样。


move.png
  • 针对 2,通过移动 bucket 内容,使其倾向于紧密排列从而提高 bucket 利用率。 sameSizeGrow,即是不改变大小的扩容动作。

4.3 扩容的迁移过程

扩容最核心的就是迁移过程。迁移过程中也区分了上述两个情况。
看一个网上的图片,画的很棒:


move-process.png

图片来自 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” 提问留言,或者加入知识星球“链人成长” 与我深度链接~

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342

推荐阅读更多精彩内容