内容简介:在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 底层公用
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Open Data Structures
Pat Morin / AU Press / 2013-6 / USD 29.66
Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues......一起来看看 《Open Data Structures》 这本书的介绍吧!