（四）golang map 源码分析

基础知识

map声明和初始化

var a map[string]string
b := make(map[string]int)

map的key一定要是可比较的类型

Golang中是没有引用传递的，均为值传递。这意味着传递的是数据的拷贝。
那么map本身是引用类型，作为形参或返回参数的时候，传递的是地址的拷贝，扩容时也不会改变这个地址。

map的操作

a = make(map[int]string)
a["a"] = "b" # 赋值
delete(a,”a“) # 删除

源码

map 源码地址：https://github.com/golang/go/blob/master/src/runtime/map.go

type hmap struct {
    count        int  //元素个数
    flags        uint8   
    B            uint8 //桶，最大可容纳的元素数量，值为 负载因子（默认 6.5） * 2 ^ B，是 2 的指数
    noverflow    uint16 //溢出 bucket 个数
    hash0        uint32 //hash 种子
    buckets      unsafe.Pointer //2^B个bucket数组指针 保存当前桶数据的指针地址 
    oldbuckets   unsafe.Pointer //扩容时旧的buckets 数组指针
    nevacuate    uintptr  //扩容搬迁进度
    extra        *mapextra //记录溢出相关
}

type mapextra struct {
    overflow    *[]*bmap //（当前）溢出桶的指针地址
    oldoverflow *[]*bmap //（旧）溢出桶的指针地址
    nextOverflow *bmap //为空闲溢出桶的指针地址
}

bucket数据结构

type bmap struct {
    tophash [bucketCnt]uint8 # bucketCnt为8 存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

map的底层结构是bmap，map是由若干个为bmap的bucket组成的数组，每个bucket可以存放若干个元素(通常是8个)，那么每个key会根据hash算法归到同一个bucket中，当一个bucket中的元素超过8个的时候，hmap会使用extra中的overflow来扩展存储key桶，最大可容纳的元素数量，值为 负载因子（默认 6.5） * 2 ^ B，是 2 的指数.

496DD5EB-04E0-41F1-82A8-E89283A7CD0D.png

map 查找过程如下：

1. 跟据key值算出哈希值 。
2. 取哈希值低位与hmpa.B取模确定bucket位置。
3. 取哈希值高位在tophash数组中查询。
4. 如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较。
5. 当前bucket没有找到，则继续从下个overflow的bucket中查找。
6. 如果当前处于搬迁过程，则优先从oldbuckets查找
   注：如果查找不到，也不会返回空值，而是返回相应类型的0值。

map 更新/插入过程如下：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

1. 跟据key值算出哈希值 。
2. 取哈希值低位与hmap.B取模确定bucket位置 。
3. 查找该key是否已经存在，如果存在则直接更新值 。4. 如果没找到将key，将key插入。

map 删除过程如下：

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

1、查找key。
2、找到key，把对应的tophash里面的打上空的标记

map 扩容策略

负载因子 = 键数量/bucket数量
哈希因子过小，说明空间利用率低
哈希因子过大，说明冲突严重，存取效率低

增量扩容

当负载因子过大时，就新建一个bucket。

等量扩容

等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高。

https://blog.csdn.net/u011957758/article/details/82846609