go map数据结构和源码详解
目录
1. 前言
2. go map的数据结构
2.1 核心结体体
2.2 数据结构图
3. go map的常用操作
3.1 创建
3.2 插入或更新
3.3 删除
3.4 查找
3.5 range迭代
3.5.1 初始化迭代器mapiterinit()
3.5.2 迭代过程mapiternext()
4. go map的扩容缩容
4.1 扩容缩容的基本原理
4.2 为什么叫“伪缩容”？如何实现“真缩容”？
5 Q&A关键知识点
5.1 基本原理
5.2 时间复杂度和空间复杂度分析
1. 前言
本文以go1.12.5版本分析，map相关的源码在runtime包的map开头的几个文件中，主要为map.go。
go的map底层实现方式是hash表（C++的map是红黑树实现，而C++ 11新增的unordered_map则与go的map类似，都是hash实现）。go map的数据被置入一个由桶组成的有序数组中，每个桶最多可以存放8个key/value对。key的hash值(32位)的低阶位用于在该数组中定位到桶，而高8位则用于在桶中区分key/value对。
go map的hash表中的基本单位是桶，每个桶最多存8个键值对，超了，则会链接到额外的溢出桶。所以go map是基本数据结构是hash数组+桶内的key-value数组+溢出的桶链表
当hash表超过阈值需要扩容增长时，会分配一个新的数组，新数组的大小一般是旧数组的2倍。这里从旧数组将数据迁移到新数组，不会一次全量拷贝，go会在每次读写Map时以桶为单位做动态搬迁疏散。
2. go map的数据结构
我们先了解基本的数据结构，后面再看源码就简单多了。
2.1 核心结体体
map主要由两个核心的结构，即基础结构和桶实现：
hmap：map的基础结构
bmap：严格来说hmap.buckets指向桶组成的数组，每个桶的头部是bmap，之后是8个key，再是8个value，最后是1个溢出指针。溢出指针指向额外的桶链表，用于存储溢出的数据
const ( // 关键的变量
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits // 一个桶最多存储8个key-value对
loadFactorNum = 13 // 扩散因子：loadFactorNum / loadFactorDen = 6.5。
loadFactorDen = 2 // 即元素数量 >= (hash桶数量(2^hmp.B) * 6.5 / 8) 时，触发扩容
)
// map的基础数据结构
type hmap struct {
count int // map存储的元素对计数，len()函数返回此值，所以map的len()时间复杂度是O(1)
flags uint8 // 记录几个特殊的位标记，如当前是否有别的线程正在写map、当前是否为相同大小的增长（扩容/缩容？）
B uint8 // hash桶buckets的数量为2^B个
noverflow uint16 // 溢出的桶的数量的近似值
hash0 uint32 // hash种子
buckets unsafe.Pointer // 指向2^B个桶组成的数组的指针，数据存在这里
oldbuckets unsafe.Pointer // 指向扩容前的旧buckets数组，只在map增长时有效
nevacuate uintptr // 计数器，标示扩容后搬迁的进度
extra *mapextra // 保存溢出桶的链表和未使用的溢出桶数组的首地址
}
// 桶的实现结构
type bmap struct {
// tophash存储桶内每个key的hash值的高字节
// tophash[0] < minTopHash表示桶的疏散状态
// 当前版本bucketCnt的值是8，一个桶最多存储8个key-value对
tophash [bucketCnt]uint8
// 特别注意：
// 实际分配内存时会申请一个更大的内存空间A，A的前8字节为bmap
// 后面依次跟8个key、8个value、1个溢出指针
// map的桶结构实际指的是内存空间A
}
// map.go里很多函数的第1个入参是这个结构，从成员来看很明显，此结构标示了键值对和桶的大小等必要信息
// 有了这个结构的信息，map.go的代码就可以与键值对的具体数据类型解耦
// 所以map.go用内存偏移量和unsafe.Pointer指针来直接对内存进行存取，而无需关心key或value的具体类型
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // internal type representing a hash bucket
keysize uint8 // size of key slot
valuesize uint8 // size of value slot
bucketsize uint16 // size of bucket
flags uint32
}
C++使用模板可以根据不同的类型生成map的代码。
golang则通过上述maptype结构体传递键值对的类型大小等信息，从而map.go直接用指针操作对应大小的内存来实现全局一份map代码同时适用于不同类型的键值对。这点上可以认为相比C++用模板实现map的方式，go map的目标文件的代码量会更小。
2.2 数据结构图
map底层创建时，会初始化一个hmap结构体，同时分配一个足够大的内存空间A。其中A的前段用于hash数组，A的后段预留给溢出的桶。于是hmap.buckets指向hash数组，即A的首地址；hmap.extra.nextOverflow初始时指向内存A中的后段，即hash数组结尾的下一个桶，也即第1个预留的溢出桶。所以当hash冲突需要使用到新的溢出桶时，会优先使用上述预留的溢出桶，hmap.extra.nextOverflow依次往后偏移直到用完所有的溢出桶，才有可能会申请新的溢出桶空间。
上图中，当需要分配一个溢出桶时，会优先从预留的溢出桶数组里取一个出来链接到链表后面，这时不需要再次申请内存。但当预留的桶被用完了，则需要申请新的内存给溢出桶。
3. go map的常用操作
3.1 创建
使用make(map[k]v, hint)创建map时会调用makemap()函数，代码逻辑比较简单。
值得注意的是，makemap()创建的hash数组，数组的前面是hash表的空间，当hint >= 4时后面会追加2^(hint-4)个桶，之后再内存页帧对齐又追加了若干个桶（参见2.2章节结构图的hash数组部分）
所以创建map时一次内存分配既分配了用户预期大小的hash数组，又追加了一定量的预留的溢出桶，还做了内存对齐，一举多得。
// make(map[k]v, hint), hint即预分配大小
// 不传hint时，如用new创建个预设容量为0的map时，makemap只初始化hmap结构，不分配hash数组
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 省略部分代码
// 随机hash种子
h.hash0 = fastrand()
// 2^h.B 为大于hint*6.5(扩容因子)的最小的2的幂
B := uint8(0)
// overLoadFactor(hint, B)只有一行代码：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
// 即B的大小应满足 hint <= (2^B) * 6.5
// 一个桶能存8对key-value，所以这就表示B的初始值是保证这个map不需要扩容即可存下hint个元素对的最小的B值
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 这里分配hash数组
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
// makeBucketArray()会在hash数组后面预分配一些溢出桶，
// h.extra.nextOverflow用来保存上述溢出桶的首地址
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
// 分配hash数组
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b) // base代表用户预期的桶的数量，即hash数组的真实大小
nbuckets := base // nbuckets表示实际分配的桶的数量，>= base，这就可能会追加一些溢出桶作为溢出的预留
if b >= 4 {
// 这里追加一定数量的桶，并做内存对齐
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}
// 后面的代码就是申请内存空间了，此处省略
// 这里大家可以思考下这个数组空间要怎么分配，其实就是n*sizeof(桶)，所以：
// 每个桶前面是8字节的tophash数组，然后是8个key，再是8个value，最后放一个溢出指针
// sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8
return buckets, nextOverflow
}
3.2 插入或更新
go map的插入操作，调用mapassign()函数。
同学们或许在某些资料上了解过：
go map需要初始化才能使用，对空map插入会panic。hmap指针传递的方式，决定了map在使用前必须初始化
go map不支持并发读写，会panic。如果一定要并发，请用sync.Map或自己解决冲突
上述两个限制，在mapassign()函数开头能找到答案：
参数合法性检测，计算hash值
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 不熟悉指针操作的同学，用指针传参往往会踩空指针的坑
// 这里大家可以思考下，为什么h要非空判断？
// 如果一定要在这里支持空map并检测到map为空时自动初始化，应该怎么写？
// 提示：指针的指针
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
// 在这里做并发判断，检测到并发写时，抛异常
// 注意：go map的并发检测是伪检测，并不保证所有的并发都会被检测出来。而且这玩意是在运行期检测。
// 所以对map有并发要求时，应使用sync.map来代替普通map，通过加锁来阻断并发冲突
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
hash := alg.hash(key, uintptr(h.hash0)) // 这里得到uint32的hash值
h.flags ^= hashWriting // 置Writing标志，key写入buckets后才会清除标志
if h.buckets == nil { // map不能为空，但hash数组可以初始是空的，这里会初始化
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
...
}
定位key在hash表中的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
again:
bucket := hash & bucketMask(h.B) // 这里用hash值的低阶位定位hash数组的下标偏移量
if h.growing() {
growWork(t, h, bucket) // 这里是map的扩容缩容操作，我们在第4章单独讲
}
// 通过下标bucket，偏移定位到具体的桶
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash) // 这里取高8位用于在桶内定位键值对
...
}
进一步定位key可以插入的桶及桶中的位置
两轮循环，外层循环遍历hash桶及其指向的溢出链表，内层循环则在桶内遍历（一个桶最多8个key-value对）
有可能正好链表上的桶都满了，这时inserti为nil，第4步会链接一个新的溢出桶进来
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
var inserti *uint8 // tophash插入位置
var insertk unsafe.Pointer // key插入位置
var val unsafe.Pointer // value插入位置
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && inserti == nil {
// 找到个空位，先记录下tophash、key、value的插入位置
// 但要遍历完才能确定要不要插入到这个位置，因为后面有可能有重复的元素
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
}
if b.tophash[i] == emptyRest {
break bucketloop // 遍历完整个溢出链表，退出循环
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !alg.equal(key, k) {
continue
}
// 走到这里说明map里找到一个重复的key，更新key-value，跳到第5步
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done // 更新Key后跳到第5步
}
ovf := b.overflow(t)
if ovf == nil {
break // 遍历完整个溢出链表，没找到能插入的空位，结束循环，下一步再追加一个溢出桶进来
}
b = ovf // 继续遍历下一个溢出桶
}
...
}
插入key
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
// 这里判断要不要扩容，我们第4章再讲
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
if inserti == nil { // inserti == nil说明上1步没找到空位，整个链表是满的，这里添加一个新的溢出桶上去
newb := h.newoverflow(t, b) // 分配新溢出桶，优先用3.1章节预留的溢出桶，用完了则分配一个新桶内存
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
val = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 当key或value的类型大小超过一定值时，桶只存储key或value的指针。这里分配空间并取指针
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectvalue() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(val) = vmem
}
typedmemmove(t.key, insertk, key) // 在桶中对应位置插入key
*inserti = top // 插入tophash，hash值高8位
h.count++ // 插入了新的键值对，h.count数量+1
...
}
结束插入
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
done:
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting // 释放hashWriting标志位
if t.indirectvalue() {
val = *((*unsafe.Pointer)(val))
}
return val // 返回value可插入位置的指针，注意，value还没插入
}
只插入了tophash和key，就结束了吗？value还没插入呢
是的，mapassign()只插入tophash和key，并返回val指针，编译器会在调用mapassign()后用汇编往val插入value
google大佬这么骚气的操作，是为了减少value值传递的次数吗？
3.3 删除
删除与插入类似，前面的步骤都是参数和状态判断、定位key-value位置，然后clear对应的内存。不展开说。以下是几个关键点：
删除过程中也会置hashWriting标志
当key/value过大时，hash表里存储的是指针，这时候用软删除，置指针为nil，数据交给gc去删。当然，这是map的内部处理，外层是无感知的，拿到的都是值拷贝
无论Key/value是值类型还是指针类型，删除操作都只影响hash表，外层已经拿到的数据不受影响。尤其是指针类型，外层的指针还能继续使用
由于定位key位置的方式是查找tophash，所以删除操作对tophash的处理是关键：
map首先将对应位置的tophash[i]置为emptyOne，表示该位置已被删除
如果tophash[i]不是整个链表的最后一个，则只置emptyOne标志，该位置被删除但未释放，后续插入操作不能使用此位置
如果tophash[i]是链表最后一个有效节点了，则把链表最后面的所有标志为emptyOne的位置，都置为emptyRest。置为emptyRest的位置可以在后续的插入操作中被使用。
这种删除方式，以少量空间来避免桶链表和桶内的数据移动。事实上，go 数据一旦被插入到桶的确切位置，map是不会再移动该数据在桶中的位置了。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
...
b.tophash[i] = emptyOne // 先标记删除
// 如果b.tophash[i]不是最后一个元素，则暂时先占着坑。emptyOne标记的位置暂时不能被插入新元素(见3.2章节插入函数)
if i == bucketCnt-1 {
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
for { // 如果b.tophash[i]是最后一个元素，则把末尾的emptyOne全部清除置为emptyRest
b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {
break // beginning of initial bucket, we're done.
}
// Find previous bucket, continue at its last entry.
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
...
}
3.4 查找
查找操作由mapaccess开头的一组函数实现。前面的章节在插入和删除之前都得先定位查找到元素，逻辑是类似的，也比较简单，就不细说了：
mapaccess1()：通过Key查找，返回value指针，用于val := map[key]。未找到时返回value类型的0值。
mapaccess2()：通过key查找，返回value指针，以及bool类型的是否查找成功的标志，用于val, ok := map[key]。未找到时返回value类型的0值。
mapaccessK()：通过key查找，返回key和value指针，用于迭代器(range)。未找到时返回空指针
mapaccess1_fat()，对mapaccess1()的封装，区别是mapaccess1_fat()多了个zero参数，未找到时返回zero
mapaccess2_fat()，也是对mapaccess1()的封装。相比mapaccess1_fat()，本函数增加一个是否查找成功的标志
3.5 range迭代
map的迭代是通过hiter结构和对应的两个辅助函数实现的。hiter结构由编译器在调用辅助函数之前创建并传入，每次迭代结果也由hiter结构传回。下方的it即是hiter结构体的指针变量。
3.5.1 初始化迭代器mapiterinit()
mapiterinit()函数主要是决定我们从哪个位置开始迭代，为什么是从哪个位置，而不是直接从hash数组头部开始呢？《go程序设计语言》好像提到过，hash表中数据每次插入的位置是变化的（其实是因为实现的原因，一方面hash种子是随机的，这导致相同的数据在不同的map变量内的hash值不同；另一方面即使同一个map变量内，数据删除再添加的位置也有可能变化，因为在同一个桶及溢出链表中数据的位置不分先后），所以为了防止用户错误的依赖于每次迭代的顺序，map作者干脆让相同的map每次迭代的顺序也是随机的。
迭代顺序随机的实现方式也简单，直接从随机的一个位置开始就行了：
it.startBucket：这个是hash数组的偏移量，表示遍历从这个桶开始
it.offset：这个是桶内的偏移量，表示每个桶的遍历都从这个偏移量开始
于是，map的遍历过程如下：
从hash数组中第it.startBucket个桶开始，先遍历hash桶，然后是这个桶的溢出链表。
之后hash数组偏移量+1，继续前一步动作。
遍历每一个桶，无论是hash桶还是溢出桶，都从it.offset偏移量开始。（如果只是随机一个开始的桶，range结果还是有序的；但每个桶都加it.offset偏移，这个输出结果就有点扑朔迷离，大家可以亲手试下，对同一个map多次range）
当迭代器经过一轮循环回到it.startBucket的位置，结束遍历。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
...
// 随机一个偏移量来开始
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))
...
mapiternext(it) // 初始化迭代器的同时也返回第1对key/value
}
3.5.2 迭代过程mapiternext()
上一节迭代循环的过程很清晰了，这里我们说明几个重要的参数：
it.startBucket：开始的桶
it.offset：每个桶开始的偏移量
it.bptr：当前遍历的桶
it.i：it.bptr已经遍历的键值对数量，i初始为0，当i=8时表示这个桶遍历完了，将it.bptr移向下一个桶
it.key：每次迭代的结果
it.value：每次迭代的结果
此外，迭代还需要关注扩容缩容的情况：
如果是在迭代开始后才growing，这种情况当前的逻辑没处理，迭代有可能异常。呃，go map不支持并发。
如果是先growing，再开始迭代，这是有可能的。这种情况下，会先到旧hash表中检查key对应的桶有没有被疏散，未疏散则遍历旧桶，已疏散则遍历新hash表里对应的桶。
4. go map的扩容缩容
4.1 扩容缩容的基本原理
go map的扩容缩容都是grow相关的函数，这里扩容是真的，缩容是伪缩容，后面我会解释。我们先看下触发条件：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
...
}
//