内容简介:在golang中,它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。
Dig101: dig more, simplified more and know more
在golang中, map
是一个不可或缺的存在。
它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。
这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。
我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。
希望看完后,会让你对 map 有更清晰的理解。网上有很多不错的源码分析,会附到文末。
本文分析基于Mac平台上 go1.14beta1
版本。
我们先简单过下map实现hash表所用的数据结构,这样方便后边讨论。
0x01 map的内部结构
在这里我们先弄清楚map实现的整体结构
map本质是hash表( hmap
),指向一堆桶( buckets
)用来承接数据,每个桶( bmap
)能存8组k/v。
当有数据读写时,会用 key
的hash找到对应的桶。
为加速hash定位桶, bmap
里记录了 tophash
数组(hash的高8位)
hash表就会有哈希冲突的问题(不同key的hash值一样,即hash后都指向同一个桶),为此map使用桶后链一个溢出桶( overflow
)链表来解决当桶8个单元都满了,但还有数据需要存入此桶的问题。
剩下 noverflow,oldbuckets,nevacuate,oldoverflow
会用于扩容,暂时先不展开
具体对应的数据结构详细注释如下:
(虽然多,先大致过一遍,后边遇到会在提到)
// runtime/map.go // A header for a Go map. type hmap struct { //用于len(map) count int //标志位 // iterator = 1 // 可能有遍历用buckets // oldIterator = 2 // 可能有遍历用oldbuckets,用于扩容期间 // hashWriting = 4 // 标记写,用于并发写入检测 // sameSizeGrow = 8 // 用于等大小buckets扩容,减少overflow桶 flags uint8 // 代表可以最多容纳loadFactor * 2^B个元素(loadFactor=6.5) B uint8 // overflow桶的计数,当其接近1<<15 - 1时为近似值 noverflow uint16 // 随机的hash种子,每个map不一样,减少哈希碰撞的几率 hash0 uint32 // 当前桶,长度为(0-2^B) buckets unsafe.Pointer // 如果存在扩容会有扩容前的桶 oldbuckets unsafe.Pointer // 迁移数,标识小于其的buckets已迁移完毕 nevacuate uintptr // 额外记录overflow桶信息,不一定每个map都有 extra *mapextra } // 额外记录overflow桶信息 type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap // 指向下一个可用overflow桶 nextOverflow *bmap } const( // 每个桶8个k/v单元 BUCKETSIZE = 8 // k或v类型大小大于128转为指针存储 MAXKEYSIZE = 128 MAXELEMSIZE = 128 ) // 桶结构 (字段会根据key和elem类型动态生成,见下边bmap) type bmap struct { // 记录桶内8个单元的高8位hash值,或标记空桶状态,用于快速定位key // emptyRest = 0 // 此单元为空,且更高索引的单元也为空 // emptyOne = 1 // 此单元为空 // evacuatedX = 2 // 用于表示扩容迁移到新桶前半段区间 // evacuatedY = 3 // 用于表示扩容迁移到新桶后半段区间 // evacuatedEmpty = 4 // 用于表示此单元已迁移 // minTopHash = 5 // 最小的空桶标记值,小于其则是空桶标志 tophash [bucketCnt]uint8 } // cmd/compile/internal/gc/reflect.go // func bmap(t *types.Type) *types.Type { // 每个桶内k/v单元数是8 type bmap struct{ topbits [8]uint8 //tophash keys [8]keytype elems [8]elemtype // overflow 桶 // otyp 类型为指针*Type, // 若keytype及elemtype不含指针,则为uintptr // 使bmap整体不含指针,避免gc去scan此类map overflow otyp }
这里有几个字段需要解释一下:
- hmap.B
这个为啥用2的对数来表示桶的数目呢?
这里是为了hash定位桶及扩容方便
比方说, hash%n
可以定位桶, 但 %
操作没有位运算快。
而利用 n=2^B,则hash%n=hash&(n-1)
则可优化定位方式为: hash&(1<<B-1)
, (1<<B-1)
即源码中 BucketMask
再比方扩容, hmap.B=hmap.B+1
即为扩容到二倍
- bmap.keys, bmap.elems
在桶里存储k/v的方式不是一个k/v一组, 而是k放一块,v放一块。
这样的相对k/v相邻的好处是,方便内存对齐。比如 map[int64]int8
, v是 int8
,放一块就避免需要额外内存对齐。
另外对于大的k/v也做了优化。
正常情况key和elem直接使用用户声明的类型,但当其size大于128( MAXKEYSIZE/MAXELEMSIZE
)时,
则会转为指针去存储。(也就是 indirectkey、indirectelem
)
- hmap.extra
这个额外记录溢出桶意义在哪?
具体是为解决让 gc
不需要扫描此类 bucket
。
只要bmap内不含指针就不需gc扫描。
当 map
的 key
和 elem
类型都不包含指针时,但其中的 overflow
是指针。
此时bmap的生成函数会将 overflow
的类型转化为 uintptr
。
而 uintptr
虽然是地址,但不会被 gc
认为是指针,指向的数据有被回收的风险。
此时为保证其中的 overflow
指针指向的数据存活,就用 mapextra
结构指向了这些 buckets
,这样bmap有被引用就不会被回收了。
关于uintptr可能被回收的例子,可以看下 go101 - Type-Unsafe Pointers 中 Some Facts in Go We Should Know
0x02 map的hash方式
了解map的基本结构后,我们通过下边代码分析下map的hash
var m = map[interface{}]int{} var i interface{} = []int{} //panic: runtime error: hash of unhashable type []int println(m[i]) //panic: runtime error: hash of unhashable type []int delete(m, i)
为什么不可以用 []int
作为key呢?
查找源码中hash的调用链注释如下:
// runtime/map.go // mapassign,mapaccess1中 获取key的hash hash := t.hasher(key, uintptr(h.hash0)) // cmd/compile/internal/gc/reflect.go func dtypesym(t *types.Type) *obj.LSym { switch t.Etype { // ../../../../runtime/type.go:/mapType case TMAP: ... // 依据key构建hash函数 hasher := genhash(t.Key()) ... } } // cmd/compile/internal/gc/alg.go func genhash(t *types.Type) *obj.LSym { switch algtype(t) { ... //具体针对interface调用interhash case AINTER: return sysClosure("interhash") ... } } // runtime/alg.go func interhash(p unsafe.Pointer, h uintptr) uintptr { //获取interface p的实际类型t,此处为slice a := (*iface)(p) tab := a.tab t := tab._type // slice类型不可比较,没有equal函数 if t.equal == nil { panic(errorString("hash of unhashable type " + t.string())) } ... }
如上,我们会发现map的hash函数并不唯一。
它会对不同key类型选取不同的hash方式,以此加快hash效率
这个例子 slice
不可比较,所以不能作为key。
也对,不可比较的类型作为key的话,找到桶但没法比较key是否相等,那map用这个key读写都会是个问题。
还有哪些不可比较?
cmd/compile/internal/gc/alg.go
的 algtype1
函数中可以找到返回 ANOEQ
(不可比较类型)的类型,如下:
- func,map,slice
- 内部元素有这三种类型的array和struct类型
0x03 map的扩容方式
map
不可以对其值取地址;
如果值类型为 slice
或 struct
,不能直接操作其内部元素
我们用代码验证如下:
m0 := map[int]int{} // :negative_squared_cross_mark: cannot take the address of m0[0] _ = &m0[0] m := make(map[int][2]int) // :white_check_mark: m[0] = [2]int{1, 0} // :negative_squared_cross_mark: cannot assign to m[0][0] m[0][0] = 1 // :negative_squared_cross_mark: cannot take the address of m[0] _ = &m[0] type T struct{ v int } ms := make(map[int]T) // :white_check_mark: ms[0] = T{v: 1} // :negative_squared_cross_mark: cannot assign to struct field ms[0].v in map ms[0].v = 1 // :negative_squared_cross_mark: cannot take the address of ms[0] _ = &ms[0] }
为什么呢?
这是因为 map
内部有渐进式扩容,所以 map
的值地址不固定,取地址没有意义。
也因此,对于值类型为 slice
和 struct
, 只有把他们各自当做整体去赋值操作才是安全的。 go有个issue讨论过这个问题: issues-3117
针对扩容的方式,有两类,分别是:
- sameSizeGrow
过多的 overflow
使用,使用等大小的buckets重新整理,回收多余的 overflow
桶,提高map读写效率,减少溢出桶占用
这里借助 hmap.noverflow
来判断溢出桶是否过多
hmap.B<=15
时,判断是溢出桶是否多于桶数 1<<hmap.B
否则只判断溢出桶是否多于 1<<15
这也就是为啥 hmap.noverflow
,当其接近 1<<15 - 1
时为近似值, 只要可以评估是否溢出桶过多不合理就行了
- biggerSizeGrow
count/size > 6.5
(装载因子 : overLoadFactor
), 避免读写效率降低。
扩容一倍,并渐进的在赋值和删除( mapassign和mapdelete
)期间,
对每个桶重新分流到 x
(原来桶区间)和 y
(扩容后的增加的新桶区间)
这里 overLoadFactor
(count/size)是评估桶的平均装载数据能力,即map平均每个桶装载多少个k/v。
这个值太大,则桶不够用,会有太多溢出桶;太小,则分配了太多桶,浪费了空间。
6.5是测试后对map装载能力最大化的一个的选择。
源码中扩容代码注释如下:
// mapassign 中创建新bucket时检测是否需要扩容 if !h.growing() && //非扩容中 (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { // 提交扩容,生成新桶,记录旧桶相关。但不开始 // 具体开始是后续赋值和删除期间渐进进行 hashGrow(t, h) } //mapassign 或 mapdelete中 渐进扩容 bucket := hash & bucketMask(h.B) if h.growing() { growWork(t, h, bucket) } // 具体迁移工作执行,每次最多两个桶 func growWork(t *maptype, h *hmap, bucket uintptr) { // 迁移对应旧桶 // 若无迭代器遍历旧桶,可释放对应的overflow桶或k/v // 全部迁移完则释放整个旧桶 evacuate(t, h, bucket&h.oldbucketmask()) // 如果还有旧桶待迁移,再迁移一个 if h.growing() { evacuate(t, h, h.nevacuate) } }
具体扩容 evacuate
(迁移)时,判断是否要将旧桶迁移到新桶后半区间( y
)有段代码比较有趣, 注释如下:
newbit := h.noldbuckets() var useY uint8 if !h.sameSizeGrow() { // 获取hash hash := t.hasher(k2, uintptr(h.hash0)) if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) { // 这里 key != key 是指key为NaNs, // 此时 useY = top & 1 意味着有50%的几率到新桶区间 useY = top & 1 top = tophash(hash) } else { if hash&newbit != 0 { // 举例来看 若扩容前h.B=3时, newbit=1<<3 // hash&newbit != 0 则hash形如 xxx1xxx // 新hmap的BucketMask= 1<<4 - 1 (1111: 15) // 则 hash&新BucketMask > 原BucketMask 1<<3-1 (111: 7) // 所以去新桶区间 useY = 1 } } } // 补充一个 key != key 的代码示例 n1, n2 := math.NaN(), math.NaN() m := map[float64]int{} m[n1], m[n2] = 1, 2 println(n1 == n2, m[n1], m[n2]) // output: false 0 0 // 所以NaN做key没有意义。。。
弄清楚map的结构、hash和扩容,剩下的就是初始化、读写、删除和遍历了,我们就不详细展开了,简单过下。
0x04 map的初始化
map不初始化时为nil,是不可以操作的。可以通过make方式初始化
// 不指定大小 s := make(map[int]int) // 指定大小 b := make(map[int]int,10)
对于这两种map内部调用方式是不一样的
- small map
当不指定大小或者指定大小不大于8时,调用
func makemap_small() *hmap {
只需要直接在堆上初始化 hmap
和hash种子( hash0
)就行。
- bigger map
当大小大于8, 调用
func makemap(t *maptype, hint int, h *hmap) *hmap {
hint
溢出则置0
初始化 hmap
和hash种子
根据 overLoadFactor:6.5
的要求, 循环增加 h.B
, 获取 hint/(1<<h.B)
最接近 6.5的 h.B
预分配hashtable的bucket数组
h.B
大于4的话,多分配至少 1<<(h.B-4)
(需要内存对齐)个bucket,用于可能的 overflow
桶使用,
并将 h.nextOverflow
设置为第一个可用的 overflow
桶。
最后一个 overflow
桶指向 h.buckets
(方便后续判断已无 overflow
桶)
0x05 map的读取
对于map的读取有着三个函数,主要区别是返回参数不同
mapaccess1: m[k] mapaccess2: a,b = m[i] mapaccessk: 在map遍历时若grow已发生,key可能有更新,需用此函数重新获取k/v
计算key的hash,定位当前buckets里桶位置
如果当前处于扩容中,也尝试去旧桶取对应的桶,需考虑扩容前bucket大小是否为现在一半,且其所指向的桶未迁移
然后就是按照bucket->overflow链表的顺序去遍历,直至找到 tophash
匹配且key相等的记录(entry)
期间,如果key或者elem是转过指针(size大于128),需转回对应值。
map为空或无值返回elem类型的零值
0x06 map的赋值
计算key的hash,拿到对应的桶
如果此时处于扩容期间,则执行扩容 growWork
对桶bucket->overflow链表遍历
-
若有空桶(对应tophash[i]为空),则准备在此空桶存储k/v
-
若非空,且和tophash相等,且key相等,则更新对应elem
-
若无可用桶,则分配一个新的overflow桶来存储k/v, 会判断是否需要扩容
最后若使用了空桶或新 overflow
桶,则要将对应 tophash
更新回去, 如果需要的话,也更新 count
0x07 map的删除
获取待删除key对应的桶,方式和mapassign的查找方式基本一样,找到则清除k/v。
这里还有个额外操作:
如果当前tophash状态是:当前cell为空( emptyOne
),
若其后桶或其后的overflow桶状态为:当前cell为空前索引高于此cell的也为空( emptyRest
),则将当前状态也更新为 emptyRest
倒着依次往前如此处理,实现 emptyOne -> emptyRest
的转化
这样有什么好处呢?
答案是为了方便读写删除( mapaccess,mapassign,mapdelete
)时做桶遍历( bucketLoop
)能减少不必要的空bucket遍历
截取代码如下:
bucketloop: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // 减少空cell的遍历 if b.tophash[i] == emptyRest { break bucketloop } continue } ... }
0x08 map的遍历
先调用 mapiterinit
初始化用于遍历的 hiter
结构体, 这里会用随机定位出一个起始遍历的桶 hiter.startBucket
, 这也就是为啥map遍历无序。
随机获取起始桶的代码如下:
r := uintptr(fastrand()) // 随机数不够用得再加一个32位 if h.B > 31-bucketCntBits { r += uintptr(fastrand()) << 31 } it.startBucket = r & bucketMask(h.B)
在调用 mapiternext
去实现遍历, 遍历中如果处于扩容期间,如果当前桶已经迁移了,那么就指向新桶,没有迁移就指向旧桶
至此,map的内部实现我们就过完了。里边有很多优化点,设计比较巧妙,需要多体会一番。
趁热打铁,你可以去阅读一遍源码,加深一下理解。
附上几篇不错的源码分析文章,代码对应的 go
版本和本文不一致,但变化不大,可以对照着看。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 洞察设计模式的底层逻辑
- 底层原理:垃圾回收算法是如何设计的?
- Go 之读懂 interface 的底层设计
- Go 之读懂 interface 的底层设计
- JavaWeb_Vue_Pro v1.7.3 旗舰版发布,重写底层架构设计,增强稳定性
- avue 1.5.2 优化大量底层代码,crud 和 form 底层公用
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。