Golang map

前些天看了DAVE CHENEY大神的直播。里面讲到了go的map实现。做个笔记

(我用的是go1.13 貌似大神直播时候用的是还没发布的1.15 所以本文中的代码都是1.13中的。与1.15略有差异)

compile time rewriting:

左边对map的操作实际上被编译成了右边的调用
v := m["key"]      -> runtime.mapaccess1(m, "key", &v)
v, ok := m["key"]  -> runtime.mapaccess2(m, "key", &v, &ok)
m["key"] = 9001    -> runtime.mapinsert(m, "key", 9001)
delete(m, "key")   -> runtime.mapdelete(m, "key")

首先介绍几个基本的func和数据结构
以mapaccess1为例：第一个参数是map的类型指针，第二个是map实例的指针。第三个参数是要访问的key的指针，返回值是指向了key对应的value的指针(这里要注意一下，由于返回的是value的指针。如果调用者一直不释放对这个值的引用，那么会导致整个map一直存在，不被GC回收，长时间占用内存。)

mapaccess1

maptype

_type

typeAlg

mapaccess func

这里值得注意一下的是hash0。这里的hash0 是从G M P 中的M取到的。因为当前包是runtime。可以通过runtime. getg获取到当前的g，进而通过g.m获取到当前的m. m.fastrand[0] 和 m.fastrand[1]

看到这里可能有人会有疑问了。hash的值并没有取低位，为什么就是用hash的低位来计算在哪个bucket中呢？这就要看h.B了：

hmap

Map每扩充一次容量增大一倍，h.B代表了这个map扩充了几次，可以算出map的buckets个数。与h.B位运算即可算出当前的这个key应该在哪个bucket中

然后就要看元素在bucket中的存储结构了。

Bucket中key和value的存储是按照 Key0 Key1 Key2 Key3 Key4 Key5 Key6 Key7/Value0Value01Value2Value3 Value4 Value5 Value6 Value7的顺序存储的而不是按照key,value/key,value这样的顺序，考虑到map[int64]uint8这种类型，如果用后者存储会浪费很多空间。

map read value

Map的扩充：

LoadFactor

LoadFactor=map.size / 2^B = 6.5
LoadFactor 越小空间使用率越低会生成更多的buckets。但是访问效率会变高， LoadFactor 越大空间使用率越高，但是访问效率会下降。
作者取了个相对适中的值 6.5
当需要扩容时，会将bucket数组的数量扩充一倍，产生新的buckets数据，并将旧的数据迁移至新的数组。扩容时map不会立即把新数据全部迁移过去，而是在访问到旧的bucket的是时候才把旧数据迁移过去，而且旧的bucket中的数据不会被删除只是加上一个删除标记，由GC来回收。

以上就是go map的大体结构和实现方法了。

总结一下：

go的map是使用数组+链表的形式实现的。
通过key的hash来决定在哪个bucket中。
每个bucket可以放8对key,value。每个bucket会保存指向下一个bucket的指针，放不下的元素会放在后续的指针指向的bucket中
Hash中的random seed 是从G->M中取到的。
Map返回的值的引用如果不释放会导致整个map一直存在。

最后编辑于：2020.05.12 10:56:18