Dig101: dig more, simplified more and know more
在 golang 中,map
是一个不可或缺的存在。
它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。
这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。
我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。
希望看完后,会让你对 map 的理解有一些帮助。网上也有很多不错的源码分析,会附到文末,感兴趣的同学自行查看下。
(本文分析基于 Mac 平台上 go1.14beta1 版本。长文预警 ... )
我们先简单过下 map 实现 hash 表所用的数据结构,这样方便后边讨论。
在这里我们先弄清楚 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
}
这里有几个字段需要解释一下:
这个为啥用 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
即为扩容到二倍
在桶里存储 k/v 的方式不是一个 k/v 一组, 而是 k 放一块,v 放一块。
这样的相对 k/v 相邻的好处是,方便内存对齐。比如map[int64]int8
, v 是int8
,放一块就避免需要额外内存对齐。
另外对于大的 k/v 也做了优化。
正常情况 key 和 elem 直接使用用户声明的类型,但当其 size 大于 128(MAXKEYSIZE/MAXELEMSIZE
)时,
则会转为指针去存储。(也就是indirectkey、indirectelem
)
这个额外记录溢出桶意义在哪?
具体是为解决让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
了解 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
(不可比较类型)的类型,如下:
map
不可以对其值取地址;
如果值类型为slice
或struct
,不能直接操作其内部元素
我们用代码验证如下:
m0 := map[int]int{}
// ❎ cannot take the address of m0[0]
_ = &m0[0]
m := make(map[int][2]int)
// ✅
m[0] = [2]int{1, 0}
// ❎ cannot assign to m[0][0]
m[0][0] = 1
// ❎ cannot take the address of m[0]
_ = &m[0]
type T struct{ v int }
ms := make(map[int]T)
// ✅
ms[0] = T{v: 1}
// ❎ cannot assign to struct field ms[0].v in map
ms[0].v = 1
// ❎ cannot take the address of ms[0]
_ = &ms[0]
}
为什么呢?
这是因为map
内部有渐进式扩容,所以map
的值地址不固定,取地址没有意义。
也因此,对于值类型为slice
和struct
, 只有把他们各自当做整体去赋值操作才是安全的。go 有个 issue 讨论过这个问题:issues-3117
针对扩容的方式,有两类,分别是:
过多的overflow
使用,使用等大小的 buckets 重新整理,回收多余的overflow
桶,提高 map 读写效率,减少溢出桶占用
这里借助hmap.noverflow
来判断溢出桶是否过多
hmap.B<=15
时,判断是溢出桶是否多于桶数1<<hmap.B
否则只判断溢出桶是否多于 1<<15
这也就是为啥hmap.noverflow
,当其接近1<<15 - 1
时为近似值, 只要可以评估是否溢出桶过多不合理就行了
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 和扩容,剩下的就是初始化、读写、删除和遍历了,我们就不详细展开了,简单过下。
map 不初始化时为 nil,是不可以操作的。可以通过 make 方式初始化
// 不指定大小
s := make(map[int]int)
// 指定大小
b := make(map[int]int,10)
对于这两种 map 内部调用方式是不一样的
当不指定大小或者指定大小不大于 8 时,调用
func makemap_small() *hmap {
只需要直接在堆上初始化hmap
和 hash 种子(hash0
)就行。
当大小大于 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
桶)
对于 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 类型的零值
计算 key 的 hash,拿到对应的桶
如果此时处于扩容期间,则执行扩容growWork
对桶 bucket->overflow 链表遍历
若有空桶(对应 tophash[i]为空),则准备在此空桶存储 k/v
若非空,且和 tophash 相等,且 key 相等,则更新对应 elem
若无可用桶,则分配一个新的 overflow 桶来存储 k/v, 会判断是否需要扩容
最后若使用了空桶或新overflow
桶,则要将对应tophash
更新回去, 如果需要的话,也更新count
获取待删除 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
}
...
}
先调用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
版本和本文不一致,但变化不大,可以对照着看。
本文代码见 NewbMiao/Dig101-Go
欢迎关注公众号:newbmiao,获取及时更新文章。
推荐阅读:Dig101-Go 系列,挖一挖技术背后的故事。
1
hanssx 2020-03-09 23:22:10 +08:00
源码分析的都是大佬,话说 C 语言用的真是广泛,经久不衰,甚至盖住了 C++的光芒。。。
|
3
CEBBCAT 2020-03-10 02:09:43 +08:00 via Android
感谢分享,明早再看
|