Go-map

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

本文将简单讲解一下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” 提问留言,或者加入知识星球“链人成长” 与我深度链接~


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

本文来自:简书

感谢作者:aside section ._1OhGeD

查看原文:Go-map

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

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