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