（四）golang map 源码分析
2019-07-01 本文已影响0人
杰克慢
基础知识
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 查找过程如下：
- 跟据key值算出哈希值 。
- 取哈希值低位与hmpa.B取模确定bucket位置。
- 取哈希值高位在tophash数组中查询。
- 如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较。
- 当前bucket没有找到，则继续从下个overflow的bucket中查找。
- 如果当前处于搬迁过程，则优先从oldbuckets查找
注：如果查找不到，也不会返回空值，而是返回相应类型的0值。
map 更新/插入过程如下：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
- 跟据key值算出哈希值 。
- 取哈希值低位与hmap.B取模确定bucket位置 。
- 查找该key是否已经存在，如果存在则直接更新值 。4. 如果没找到将key，将key插入。
map 删除过程如下：
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
1、查找key。
2、找到key，把对应的tophash里面的打上空的标记
map 扩容策略
负载因子 = 键数量/bucket数量
哈希因子过小，说明空间利用率低
哈希因子过大，说明冲突严重，存取效率低
增量扩容
当负载因子过大时，就新建一个bucket。
等量扩容
等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高。
