为什么要研究map的实现

对于这个问题，我的回答有以下几个方面：

1. 了解工业级map的另一种实现方案，增加自己的经验，可能对自己日后的工作有借鉴意义
2. 只有了解了其实现原理才能清楚其性能瓶颈在哪，开发过程中尽量去避免

map的基本原理

map的底层结构是一个哈希表，map中的键值对被分配到了一个bucket数组上，每个bucket包含8个键值对。hash值的二进制低位部分被用来选择bucket，每个bucket存储了hash值的高位部分以用来在单个bucket上做区分。如果有超过8个key被hash到了同一个bucket上，那么就用链表连接到扩展bucket上。

底层数据结构

map 对应的结构体，一个map实际是hmap指针

type hmap struct {
	count     int // map中元素个数，即len(map)
	flags     uint8 // map的标记
	B         uint8 //bucket数量为2^B个
	noverflow uint16 // 溢出bucket的近似数量
	hash0     uint32 // hash seed 每次创建map都会生产一个随机的种子，提高hash碰撞攻击门槛
	buckets    unsafe.Pointer // bucket数组的地址，如果count=0，则有可能是nil
	oldbuckets unsafe.Pointer // 
	nevacuate  uintptr        // 指示扩容进度，小于此地址的buckets迁移完成
	extra *mapextra // optional fields
}

其中flags有以下几种标记：

bucket对应的结构体如下，源码中是没有keys、values、overflow这三个字段的，但实际运行过程内存中对应位置会有这三个字段

type bmap struct {
	tophash [8]uint8 // 如果<5表示存的是状态，>=5存的是hash值高8位
	// keys [8]keytype
	// values [8]valuetype // 之所以将key和value单独放在一起是因为内存对齐会浪费很多内存
	// overflow uintptr // 溢出桶地址
}

tophash时存的是状态，共有以下几种状态：

|常量名|值|说明| |——|——|——|——| |emptyRest|0|当前槽是空的，并且接下来的槽也是空的| |emptyOne|1|当前槽是空的，其他槽不一定| |evacuatedX|2|当前槽有效，但是已经被迁移到了扩容后buckets数组的上半区| |evacuatedY|3|当前槽有效，但是已经被迁移到了扩容后buckets数组的下半区| |evacuatedEmpty|4|当前槽是空的，已经被迁移了|

mapextra对应的结构体如下：

type mapextra struct {
	// The indirection allows to store a pointer to the slice in hiter.
	// 如果k/v都不包含指针，并且可以被inline，那么我们标记桶不含指针，这样避免gc扫描整个map
	// 然而bmap结构体的overflow字段是一个指针，为了保证溢出桶不被回收，我们用overflow存储所有hmap.buckets上的所有溢出桶，oldoverflow存储hmap.oldbuckets上的所有溢出桶
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// 创建bucket数组时会预先分配一些溢出桶出来，nextOverflow为这部分桶的第一个桶
	nextOverflow *bmap
}

它们之间的关系可以用下面这张图来表示：

map的创建

在Go中通常使用make来创建一个map，像这样：

make(map[ktype]vtype, hint)

而在Go源码中提供了三个创建map的函数，它们分别是：

func makemap_small() *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap

1. 如果不指定hint或者hint(bucketCnt，即bucket上的元素数)时Go会通过runtime.makemap_small()来创建
2. 如果hint为int64使用runtime.makemap64()来创建，但里面还是调用的runtime.makemap()
3. 否则通过调用runtime.makemap()来创建

makemap_small()的代码非常简单，就是new一个hmap对象，然后生成hash种子:

func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

而makemap()的过程就相对复杂了，步骤为：

1. 创建hmap结构体，并生成hash seed
2. 通过hint找到bucket数组的长度，其实就是找到B
3. 如果B不为0，那么就为hmap预创建bucket数组
4. 如果B>=4我们认为大概率会有溢出桶，所以会预先分配2^(b-4)个溢出桶出来，然后将hmap.extra.nextOverflow指向预分配的第一个溢出桶

代码：

// t为map的类型信息， hint即make()的第二个参数
func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 计算所需内存
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		// 如果溢出则将初始化大小修改为0
		hint = 0
	}

	// 初始化Hmap
	if h == nil {
		h = new(hmap)
	}
	// 生成hash seed, fastrand()这里不做详解，看注释是实现了某篇论文...
	h.hash0 = fastrand()

	// 找到一个 B，使得 map 的负载因子在正常范围内。
	B := uint8(0)
	for overLoadFactor(hint, B) { // overLoadFactor(hint, B) 等价于 hint > 2^B*6.5
		B++
	}
	h.B = B
	
	if h.B != 0 {
		var nextOverflow *bmap
		// 预分配bucket数组
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			// 如果预分配了溢出桶，则用h.extra.nextOverflow存第一个溢出桶的指针
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

makeBucketArray的源码

// dirtyalloc要么是nil要么是之前由makeBucketArray使用相同的t和b创建出来的bucket数组
// 如果dirtyalloc为nil，那么就会创建出一个新数组，如果不为nil则会清空掉之前的dirtyalloc然后重用这部分内存来创建新数组
// 如果b>=4我们认为大概率会有溢出桶，所以会预先分配2^(b-4)个溢出桶出来，nextOverflow即为这部分桶的第一个桶
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base
	if b >= 4 {
		// 当b>=4时大概率会有溢出桶，所以这里预先分配一些溢出桶出来
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	if dirtyalloc == nil {
		buckets = newarray(t.bucket, int(nbuckets))
	} else {
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		// 清空dirtyalloc
		if t.bucket.ptrdata != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets {
		// 进到这里说明上面申请了一些溢出桶
		// nextOverflow为第一个溢出桶的地址
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		// last为最后一个溢出桶的地址
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		// 将最后一个溢出桶的overflow设置为buckets数组的第一个元素
		// 之所以这么搞是为了方便判断h.extra.nextOverflow是不是最后一个预分配的溢出桶
		// 如果没理解的话看下下面的newoverflow函数😄
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

赋值

Go中编译器会针对不同类型的key调用不同的赋值函数，它们分别是：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

它们的实现相差不大，我们只理解mapassign()的实现就行了，mapassign()赋值的步骤如下：

1. 求key的hash值，找到其对应的bucket
2. 如果正在扩容的话，需要将该bucket迁到新数组中
3. 遍历bucket及其链接的溢出桶上的所有槽，如果找到了key，则接下来将新值赋到该槽上
4. 如果没有找到key，则写到第一个空槽上
5. 如果没有空槽则创建出来一个新的溢出桶出来，将新键值对写到这个新溢出桶上
6. 如果要没有找到key或者需要创建新溢出桶的话还需要判断是否需要扩容，如果需要的话就先进行扩容，再重复步骤2
7. 将键值对写到查询到的位置 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... // 求key的hash值 hash := t.hasher(key, uintptr(h.hash0)) ... if h.buckets == nil { // 如果map的bucket数组还没有创建则创建出来 h.buckets = newobject(t.bucket) } again: // 获取hash值的低B位 bucket := hash & bucketMask(h.B) if h.growing() { // 如果map正在扩容则调用growWork迁移bucket growWork(t, h, bucket) } // 根据低B位找到对应的bucket b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) // 取hash值的高8位，如果<5则再加上5 top := tophash(hash) var inserti *uint8 var insertk unsafe.Pointer var elem unsafe.Pointer bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // tophash不匹配 if b.tophash[i] <= emptyOne && inserti == nil { // 如果槽是空的，则记录下这个位置 inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) } if b.tophash[i] == emptyRest { // 当前槽是emptyRest，则之后的槽肯定也是空的，就不用往后查了 break bucketloop } continue } // tophash一致的话再判断key是否能匹配上 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if !t.key.equal(key, k) { // 如果key没有匹配上则继续查询 continue } // 找到了key，直接更新就行 if t.needkeyupdate() { typedmemmove(t.key, k, key) } elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) // 找到了key直接跳出循环 goto done } // 再遍历溢出桶 ovf := b.overflow(t) if ovf == nil { break } b = ovf } // 走到这里说明，当前map上没有指定的key，所以就需要写入一个新的键值对 // 如果写入新的键值对后负载系数>6.5 或者有太多溢出桶的话，就需要扩容 // 当然了，如果正在扩容中就不用再扩容了 // 溢出桶过多会严重影响查询效率所以需要扩容 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) // 扩容后需要重新找一个新的位置 goto again } if inserti == nil { // 当map上所有槽都满的情况下，上面查到的插入位置就是空了 // 所以加一个溢出桶承载新添加的键值对 newb := h.newoverflow(t, b) inserti = &newb.tophash[0] // 槽上k的位置 insertk = add(unsafe.Pointer(newb), dataOffset) // 槽上v的位置 elem = add(insertk, bucketCnt*uintptr(t.keysize)) } // 在插入位置写入新的键值对 if t.indirectkey() { // t.indirectkey()=true说明bucket存储的是key的指针 // 为key申请一块内存并返回该块内存的地址 kmem := newobject(t.key) // 将插入位置的值转为该块内存的地址 *(*unsafe.Pointer)(insertk) = kmem // insertk也指向到这块内存的地址 insertk = kmem } if t.indirectelem() { vmem := newobject(t.elem) *(*unsafe.Pointer)(elem) = vmem } // 将key写入到insertk指向的内存位置 typedmemmove(t.key, insertk, key) *inserti = top // 元素数量+1 h.count++ done: ... if t.indirectelem() { elem = *((*unsafe.Pointer)(elem)) } return elem }

newoverflow的流程：

源码：

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
	if h.extra != nil && h.extra.nextOverflow != nil {
		// 如果nextOverflow不为空，说明我们还有空闲的预分配溢出桶
		// 我们将优先使用空闲的预分配溢出桶
		ovf = h.extra.nextOverflow
		if ovf.overflow(t) == nil {
			// 如果该桶没有溢出桶，则将当前nextOverflow设置为它的下一个桶
			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
		} else {
			// 如果该桶有overflow，则说明它是最后一个溢出桶了，我们没有可用的预分配溢出桶了
			// 回忆下makeBucketArray函数，我们是不是把最后一个预分配的溢出桶的overflow设置为了buckets数组的第一个元素了😆
			// nextOverflow设置为nil
			ovf.setoverflow(t, nil)
			h.extra.nextOverflow = nil
		}
	} else {
		ovf = (*bmap)(newobject(t.bucket))
	}
	h.incrnoverflow()
	if t.bucket.ptrdata == 0 {
		// 这里如果没懂的话看下上面mapextra结构体的说明
		h.createOverflow() // 其实是初始化h.extra.overflow
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
	b.setoverflow(t, ovf)
	return ovf
}

func (h *hmap) createOverflow() {
	if h.extra == nil {
		h.extra = new(mapextra)
	}
	if h.extra.overflow == nil {
		h.extra.overflow = new([]*bmap)
	}
}

扩容

既然上面提到了扩容那就在这里总结下扩容的步骤吧

扩容的条件

1. 元素数量 / 桶数量 >= 6.5
2. 溢出桶过多，当B<15（即bucket数量<2^15）时，如果溢出桶总数>=bucket数量则判定溢出桶过多；当B>=15时，如果溢出桶总数>=2^15则判定溢出桶过多

当条件1满足时，我们扩容一倍（将B加1），当条件1不足但条件2满足时说明桶利用率比较低，元素都被分配到了溢出桶上，这时容量不变，只移动bucket来降低空槽率

扩容步骤

1. 如果负载系数>=6.5说明是由于溢出桶过多进行的扩容，这种扩容会进行等量扩容，不会增加buckets数组大小，这是将给map加上sameSizeGrow标志；否则将B+1，即扩容1倍
2. 创建一个新buckets数组，并预分配一些溢出桶，清除map的iterator和oldIterator标志，如果当前map正在被迭代，则需要给map加个oldIterator标志
3. 修改hmap结构体，将新buckets数组赋值给hmap.buckets字段，旧buckets数组赋值给hmap.oldbuckets字段，如果hmap.extra上还有溢出桶，还需要将此溢出桶赋值给hmap.extra.oldoverflow，同时hmap.extra.overflow置为nil
4. 如果预分配了溢出桶，则将第一个溢出桶赋值给hmap.extra.nextOverflow func hashGrow(t *maptype, h *hmap) { bigger := uint8(1) if !overLoadFactor(h.count+1, h.B) { // 如果负载系数>=6.5说明是由于溢出桶过多进行的扩容，同时也说明了有许多bucket没有利用上 // 这时不扩容，只rehash bigger = 0 h.flags |= sameSizeGrow } oldbuckets := h.buckets // 创建一个新bucket数组 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) // 将flags中的iterator和oldIterator位清零 flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } // 修改map h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0 if h.extra != nil && h.extra.overflow != nil { if h.extra.oldoverflow != nil { throw("oldoverflow is not nil") } h.extra.oldoverflow = h.extra.overflow h.extra.overflow = nil } if nextOverflow != nil { if h.extra == nil { h.extra = new(mapextra) } h.extra.nextOverflow = nextOverflow } }

可以看到hashGrow中是没有做迁移动作的，桶迁移是调用growWork渐进式进行的。

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// bucket是在新数组上的位置，bucket&h.oldbucketmask()是在旧数组上的位置
	evacuate(t, h, bucket&h.oldbucketmask())

	// 如果还在扩容状态则再多迁移一个oldbucket
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

evacuate源码

// oldbucket是要迁移的bucket在旧数组上的索引
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	// 索引找到要迁移的旧bucket的地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	newbit := h.noldbuckets()
	if !evacuated(b) {
		// x和y是移动的目标
		// x表示的是新bucket数组的前半部分
		// y表示的是新bucket数组的后半部分
		var xy [2]evacDst
		x := &xy[0]
		// 找到要迁移的bmap的地址
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		// 找到要迁移的k的地址
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		// 找到要迁移的v的地址
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))

		if !h.sameSizeGrow() {
			y := &xy[1]
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}

		
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.keysize))
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
				top := b.tophash[i]
				if isEmpty(top) {
					// 空槽不迁移
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				if !h.sameSizeGrow() {
					// 增量扩容的情况下，计算hash以判断我们的数据是迁移到哪部分bucket
					hash := t.hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
						// 为什么要加 reflexivekey 的判断，可以参考这里:
                        			// https://go-review.googlesource.com/c/go/+/1480
                        			// key != key，只有在 float 数的 NaN 时会出现
                        			// 比如:
                        			// n1 := math.NaN()
                        			// n2 := math.NaN()
                        			// fmt.Println(n1, n2)
                        			// fmt.Println(n1 == n2)
                        			// 这种情况下 n1 和 n2 的哈希值也完全不一样
                        			// 这里官方表示这种情况是不可复现的
                        			// 需要在 iterators 参与的情况下才能复现
                        			// 但是对于这种 key 我们也可以随意对其目标进行发配
                        			// 同时 tophash 对于 NaN 也没啥意义
                        			// 还是按正常的情况下算一个随机的 tophash
                        			// 然后公平地把这些 key 平均分布到各 bucket 就好
						useY = top & 1
						top = tophash(hash)
					} else {
						// 假设旧桶数为2，那么newbit就为100(二进制形式)
						// 新桶数为4，bucketMask为111，
						// hash&newbit != 0说明hash形式为xxx1xx，
						// hash & bucketMask肯定是>100，所以肯定在Y半区
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}

				// 修改旧桶tophash为状态值
				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
				dst := &xy[useY]                 // evacuation destination

				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
				dst.b.tophash[dst.i&(bucketCnt-1)] = top
				if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 
				} else {
					typedmemmove(t.key, dst.k, k) 
				}
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
				dst.i++
				
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
		
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

查找

runtime的map提供了mapaccess1、mapaccess2、mapaccessK三个函数来获取值，取值时编译器会将v, exists = map[k] 转化为mapaccess2，v = map[k]转化为mapaccess1，mapaccessK只用于map遍历时。下面我们以mapaccess1为例看下是如何查找key的。

mapaccess1查找的流程：

1. 计算key的hash值，hash值的低B位即为key所在bucket在map.buckets数组中的下标，通过hash值的低B位就能找到key所在bucket，如果map在扩容中那就找到key所在的旧bucket，如果旧bucket未迁移，那么接下来从旧bucket中找key
2. 遍历bucket的每个槽，取hash值的tophash(高8位)与遍历到的槽上的tophash对比，如果不同则先判断下槽上的tophash是否是emptyRest，如果是那说明当前槽即下面的槽都是空槽了，就不用遍历了，如果不是就继续查下一个槽，直到tophash匹配上
3. 如果上一步找到了匹配的tophash，就继续判断槽上的key是不是我们要找的key，如果不是还得继续遍历，如果是我们要找的key就取槽上的v返回就结束了
4. 如果上一步没有找到对应的槽，说明map上没有我们要找的key func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... if h == nil || h.count == 0 { if t.hashMightPanic() { // 这段代码是因为当从一个非空的map中取值时, // 如果key为nil, 那么会导致一个panic, // 但同样的操作在nil/空 map上就不会发生, 这可能会导致难以发现的bug // 所以这里还是要额外计算下key的hash值 t.hasher(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]) } ... // 计算key对应的hash值 // go为不同的type选择不同的hash函数，具体可以看下/cmd/compile/internal/gc/alg.go genhash()函数 hash := t.hasher(key, uintptr(h.hash0)) m := bucketMask(h.B) // 取hash值的低B位，然后找到对应的bucket b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 如果oldbuckets不为空，说明在扩容中 if c := h.oldbuckets; c != nil { if !h.sameSizeGrow() { m >>= 1 } // 找到旧bucket oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 如果还未迁移则下面从旧bucket查询key if !evacuated(oldb) { b = oldb } } // 取hash值的高8位(如果<5则再加上5) top := tophash(hash) bucketloop: // 先查找当前bucket的8个元素，再查找溢出桶上的元素 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // 如果tophash为emptyRest则说明当前槽和后面的槽都不会有元素了 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)) } // hash值一致后再判断key是否是我们要查询的key if t.key.equal(key, k) { // 取回元素值 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { e = *((*unsafe.Pointer)(e)) } return e } } } return unsafe.Pointer(&zeroVal[0]) }

删除

删除的步骤：

1. 与查找类似先通过key与hash值在bucket数组上找到对应的槽
2. 将槽上的k/v清空，并将tophash设置为emptyOne
3. 如果该槽是最后一个元素则将它及它之前的空槽tophash都设置为emptyRest，标识其后面都是空槽 func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { ... // 计算key的hash值 alg := t.key.alg hash := alg.hash(key, uintptr(h.hash0)) ... // 根据hash值低B位找到bucket索引 bucket := hash & bucketMask(h.B) if h.growing() { // 如果正在扩容则执行迁移操作 growWork(t, h, bucket) } // 找到对应的bmap b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) bOrig := b top := tophash(hash) // 下面与查询类似都是去找到具体所在的槽 search: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break search } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } if !alg.equal(key, k2) { continue } // 如果 key 中是指针，就清空 key 的内容 if t.indirectkey() { *(*unsafe.Pointer)(k) = nil } else if t.key.ptrdata != 0 { memclrHasPointers(k, t.key.size) } e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { *(*unsafe.Pointer)(e) = nil } else if t.elem.ptrdata != 0 { memclrHasPointers(e, t.elem.size) } else { memclrNoHeapPointers(e, t.elem.size) } b.tophash[i] = emptyOne // 如果该槽不是最后一个元素则跳转到最后 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 } } // 如果该槽是最后一个元素则将它及它之前的空槽tophash都设置为emptyRest，标识其后都是空槽 for { b.tophash[i] = emptyRest if i == 0 { // 如果i=0说明遍历到了该bucket上的第一个槽，这时如果遍历到的b是冲突链表上的第一个bucket说明我们已经遍历完了，break if b == bOrig { break } c := b // 从冲突链表上第一个bucket开始找当前bucket的上一个bucket for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } i = bucketCnt - 1 } else { i-- } if b.tophash[i] != emptyOne { break } } notLast: // 元素数-1 h.count-- break search } } ... }