深度解析GoLand map原理及实现，手撕源码！（二）——写入、删除、遍历

本文主要是介绍深度解析GoLand map原理及实现，手撕源码！（二）——写入、删除、遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言
本文内容承接前文：深度解析GoLand map原理及实现，手撕源码！（一）——基本介绍，初始化，读

建议先阅读前文哦~

---

4.4 写入流程 —— mapassign

写流程主要分为以下步骤：

1. 对key取hash值，再对桶数取模，确定所在的桶
2. 如果当前map处于扩容状态，采用渐进扩容，迁移命中的桶
3. 沿着桶链表遍历各个桶内的键值对
4. 如果命中key，就对value进行更新
5. 如果key不存在，就插入此键值对
6. 检查map是否达成扩容条件，如果达成，就返回第二步，承担一部分渐进扩容

写入的主要方法是 ： mapassign
源码如下：

// 类似于mapaccess，但如果map中不存在键，则为其分配一个槽位。 【mapaccess是读操作主要用到的方法】
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {if h == nil {panic(plainError("assignment to entry in nil map"))//尝试对nil map进行赋值}// 开启竞态检测、内存清理检测，地址清理检测if raceenabled {callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapassign)racewritepc(unsafe.Pointer(h), callerpc, pc)raceReadObjectPC(t.Key, key, callerpc, pc)}if msanenabled {msanread(key, t.Key.Size_)}if asanenabled {asanread(key, t.Key.Size_)}if h.flags&hashWriting != 0 {fatal("concurrent map writes")//并发的map写入}hash := t.Hasher(key, uintptr(h.hash0))// 在调用t.hasher之后设置hashWriting，因为t.hasher可能会panic，// 在这种情况下，我们实际上并没有进行写入。h.flags ^= hashWritingif h.buckets == nil {h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)}again:bucket := hash & bucketMask(h.B)if h.growing() {growWork(t, h, bucket)}b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))top := tophash(hash)var inserti *uint8var insertk unsafe.Pointervar elem unsafe.Pointer
bucketloop:for {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if isEmpty(b.tophash[i]) && 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.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 !t.Key.Equal(key, k) {continue}// 已经有了对应key的映射。更新它。if t.NeedKeyUpdate() {typedmemmove(t.Key, k, key)}elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))goto done}ovf := b.overflow(t)if ovf == nil {break}b = ovf}// 没有找到key的映射。分配新单元格并添加条目。// 如果我们达到了最大负载因子，或者我们有太多的溢出桶，// 并且我们还没有在扩容中，开始扩容。if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // 扩容表会使一切无效，所以再试一次}if inserti == nil {// 当前桶和所有连接到它的溢出桶都已满，分配一个新的。newb := h.newoverflow(t, b)inserti = &newb.tophash[0]insertk = add(unsafe.Pointer(newb), dataOffset)elem = add(insertk, bucketCnt*uintptr(t.KeySize))}// 在插入位置存储新的key/elemif t.IndirectKey() {kmem := newobject(t.Key)*(*unsafe.Pointer)(insertk) = kmeminsertk = kmem}if t.IndirectElem() {vmem := newobject(t.Elem)*(*unsafe.Pointer)(elem) = vmem}typedmemmove(t.Key, insertk, key)*inserti = toph.count++done:if h.flags&hashWriting == 0 {fatal("concurrent map writes") // 并发的map写入}h.flags &^= hashWritingif t.IndirectElem() {elem = *((*unsafe.Pointer)(elem))}return elem
}

核心代码详解

4.4.1 判断初始化，未初始化直接panic

	if h == nil {panic(plainError("assignment to entry in nil map"))//尝试对nil map进行赋值}

4.4.2 判断是否有并发写或者删除操作，有则抛出fatal error

	if h.flags&hashWriting != 0 {fatal("concurrent map writes")//并发的map写入}

4.4.3 通过 maptype.hasher() 求得 key 对应的 hash 值

	hash := t.Hasher(key, uintptr(h.hash0))

4.4.4 为map.flags添加写标记

	h.flags ^= hashWriting

• 如果 h.flags 中的 hashWriting 位当前是1（表示正在写入），这个操作会将其切换为0（表示不再写入）。
• 如果 h.flags 中的 hashWriting 位当前是0（表示没有写入），这个操作会将其切换为1（表示开始写入）。

4.4.5 判断map的桶数组buckets是否为空，为空就对其进行初始化

if h.buckets == nil {h.buckets = newobject(t.bucket) 
}

4.4.6 找到当前key对应的桶索引bucket

	bucket := hash & bucketMask(h.B)

4.4.7 判断当前map是否处于扩容过程，扩容就进行渐进式扩容

	if h.growing() {growWork(t, h, bucket)}

• 具体见后文扩容

4.4.8 从桶数组backets进行地址偏移，获得到对应的桶

b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))

4.4.9 获取tophash

top := tophash(hash)

4.4.10 声明三个指针

var inserti *uint8	//tophash 拟插入位置
var insertk unsafe.Pointer // key 拟插入位置
var elem unsafe.Pointer // val 拟插入位置

4.4.11 开启两层for循环

	for {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if isEmpty(b.tophash[i]) && 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.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 !t.Key.Equal(key, k) {continue}// 已经有了对应key的映射。更新它。if t.NeedKeyUpdate() {typedmemmove(t.Key, k, key)}elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))goto done}ovf := b.overflow(t)if ovf == nil {break}b = ovf}

这段的代码跟上一篇的双for差不多，简单解释一下：

• for循环开始，这是一个无限循环，通常用于遍历map的所有bucket
• 内部的for循环通过i变量遍历每个bucket中的条目。bucketCnt是每个bucket中可能的条目数。
• 检查当前条目的tophash是否与我们要插入或查找的键的tophash相匹配。
• 如果tophash匹配，使用add函数计算键的地址，如果键是间接存储的(t.IndirectKey())，则获取实际的键值。
• 使用!t.Key.Equal(key, k)检查当前键是否与我们要查找的键相等
• 如果当前bucket已经遍历完毕，使用b.overflow(t)检查是否有溢出bucket。

4.4.12 调整之前三个指针，用于之后的插入流程

• 在map的bucket中查找键的插入位置或者现有键的位置。如果找到了一个空位，它会记录下来，以便后续可以在这里插入新的键值对。

if b.tophash[i] != top {if isEmpty(b.tophash[i]) && 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.ValueSize))}if b.tophash[i] == emptyRest {break bucketloop}continue
}

• 倘若桶中某个位置的 tophash 标识为 emptyOne（1），说明当前位置未放入元素，倘若为 emptyRest（0），说明包括当前位置在内，此后的位置都为空。

const emptyRest = 0 
const emptyOne = 1 func isEmpty(x uint8) bool {return x <= emptyOne
}

4.4.13 判断是否找到了相等的 key，执行更新操作，并且直接跳转到方法的 done 标志位处，进行收尾处理

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))if t.IndirectKey() {k = *((*unsafe.Pointer)(k))}if !t.Key.Equal(key, k) {continue}// 已经有了对应key的映射。更新它。if t.NeedKeyUpdate() {typedmemmove(t.Key, k, key)}elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))goto done

4.4.14 判断是否找到对应的key，判断 map 是否需要开启扩容模式

开启扩容之后，这次的操作也需要承担一部分逐步扩容

	// 如果我们达到了最大负载因子，或者我们有太多的溢出桶，// 并且我们还没有在扩容中，开始扩容。if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // 扩容表会使一切无效，所以再试一次}

4.4.15 如果当前的桶都无法插入，创建一个溢出桶挂在桶链表的尾部

	if inserti == nil {// 当前桶和所有连接到它的溢出桶都已满，分配一个新的。newb := h.newoverflow(t, b)inserti = &newb.tophash[0]insertk = add(unsafe.Pointer(newb), dataOffset)elem = add(insertk, bucketCnt*uintptr(t.KeySize))}

• 如果hmap的extra字段中已经有预先分配的溢出bucket，就不再进行新建操作
• 如果没有就新建一个溢出bucket

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {var ovf *bmap // 定义一个指向bmap的指针，用于指向新的溢出桶if h.extra != nil && h.extra.nextOverflow != nil {// 我们有预先分配的溢出桶可用。// 有关更多细节，请参见makeBucketArray函数。ovf = h.extra.nextOverflow // 使用预先分配的溢出桶if ovf.overflow(t) == nil {// 我们还没有到达预先分配的溢出桶的末尾。移动指针。h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize)))} else {// 这是最后一个预先分配的溢出桶。// 重置这个桶上的溢出指针，// 该指针被设置为一个非nil的哨兵值。ovf.setoverflow(t, nil)h.extra.nextOverflow = nil}} else {ovf = (*bmap)(newobject(t.Bucket)) // 创建一个新的溢出桶}h.incrnoverflow() // 增加溢出桶的数量if t.Bucket.PtrBytes == 0 {h.createOverflow() // 创建溢出桶数组*h.extra.overflow = append(*h.extra.overflow, ovf) // 将新的溢出桶添加到数组中}b.setoverflow(t, ovf) // 设置当前桶的溢出指针指向新的溢出桶return ovf // 返回新的溢出桶
}

4.4.16 将键值对插入到空位中，并将计数器加一

	// 在插入位置存储新的key/elemif t.IndirectKey() {kmem := newobject(t.Key)*(*unsafe.Pointer)(insertk) = kmeminsertk = kmem}if t.IndirectElem() {vmem := newobject(t.Elem)*(*unsafe.Pointer)(elem) = vmem}typedmemmove(t.Key, insertk, key)*inserti = toph.count++

4.4.17 再次进行并发检测，抹除写标记

done:if h.flags&hashWriting == 0 {fatal("concurrent map writes") // 并发的map写入}h.flags &^= hashWritingif t.IndirectElem() {elem = *((*unsafe.Pointer)(elem))}return elem
}

4.5 删除 —— mapdelete

删除主要有以下几个步骤：

1. 对key取hash并取余，找到所在的桶
2. 判断map是否处于扩容状态，帮助渐进扩容
3. 遍历当前桶的键值对，命中就删除，并更新tophash值

删除的主要方法是：mapdelete
源码如下：

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {// 如果启用了竞态检测并且映射不为空，则记录写操作。if raceenabled && h != nil {// 获取调用者的程序计数器地址和当前函数的程序计数器地址。callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapdelete)// 记录写操作。racewritepc(unsafe.Pointer(h), callerpc, pc)// 读取键对象。raceReadObjectPC(t.Key, key, callerpc, pc)}// 如果启用了内存清理检测并且映射不为空，则读取键。if msanenabled && h != nil {msanread(key, t.Key.Size_)}// 如果启用了地址清理检测并且映射不为空，则读取键。if asanenabled && h != nil {asanread(key, t.Key.Size_)}// 如果映射为空或者计数为0，则可能不执行任何操作。if h == nil || h.count == 0 {// 如果哈希函数可能会引发恐慌，则调用它。if t.HashMightPanic() {t.Hasher(key, 0) // 参见问题23734}return}// 如果映射正在写入，则引发致命错误。if h.flags&hashWriting != 0 {fatal("concurrent map writes")}// 计算键的哈希值。hash := t.Hasher(key, uintptr(h.hash0))// 在调用哈希函数之后设置正在写入标志，因为哈希函数可能会引发恐慌。h.flags ^= hashWriting// 计算桶索引。bucket := hash & bucketMask(h.B)// 如果映射正在增长，则执行增长工作。if h.growing() {growWork(t, h, bucket)}// 获取桶的起始地址。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 := kif t.IndirectKey() {k2 = *((*unsafe.Pointer)(k2))}// 如果键不相等，则继续搜索。if !t.Key.Equal(key, k2) {continue}// 如果键中有指针，则清除键。if t.IndirectKey() {*(*unsafe.Pointer)(k) = nil} else if t.Key.PtrBytes != 0 {memclrHasPointers(k, t.Key.Size_)}// 计算值的地址并清除它。e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))if t.IndirectElem() {*(*unsafe.Pointer)(e) = nil} else if t.Elem.PtrBytes != 0 {memclrHasPointers(e, t.Elem.Size_)} else {memclrNoHeapPointers(e, t.Elem.Size_)}// 将顶部哈希值设置为emptyOne。b.tophash[i] = emptyOne// 如果桶现在以一堆emptyOne状态结束，则将这些状态更改为emptyRest状态。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}}// 将所有emptyOne状态更改为emptyRest状态。for {b.tophash[i] = emptyRestif i == 0 {if b == bOrig {break // 如果是初始桶的开始，则完成。}// 找到前一个桶，继续在其最后一个条目处搜索。c := bfor b = bOrig; b.overflow(t) != c; b = b.overflow(t) {}i = bucketCnt - 1} else {i--}if b.tophash[i] != emptyOne {break}}notLast:// 减少计数。h.count--// 重置哈希种子，使攻击者更难重复触发哈希冲突。if h.count == 0 {h.hash0 = fastrand()}break search}}// 如果映射没有标记为正在写入，则引发致命错误。if h.flags&hashWriting == 0 {fatal("concurrent map writes")}// 清除正在写入标志。h.flags &^= hashWriting
}

大部分代码都和之前的一样，这里只解释不一样的

4.5.1 若找到对应的key，则删除对应的键值对，并修改当前的tophash值

			// 如果键中有指针，则清除键。if t.IndirectKey() {*(*unsafe.Pointer)(k) = nil} else if t.Key.PtrBytes != 0 {memclrHasPointers(k, t.Key.Size_)}// 计算值的地址并清除它。e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))if t.IndirectElem() {*(*unsafe.Pointer)(e) = nil} else if t.Elem.PtrBytes != 0 {memclrHasPointers(e, t.Elem.Size_)} else {memclrNoHeapPointers(e, t.Elem.Size_)}// 将顶部哈希值设置为emptyOne。b.tophash[i] = emptyOne

• bucketCnt * uintptr(t.KeySize) 桶中所有键占用的总空间大小。
• i * uintptr(t.ValueSize) 到当前键之前所有值占用的空间大小。
• dataOffset 是桶中数据部分开始的偏移量
• dataOffset + bucketCnt * uintptr(t.KeySize) + i * uintptr(t.ValueSize) + dataOffset 得到从桶开始到当前值的总偏移量。
• 使用 add 函数将计算出的偏移量加到桶的起始地址 b 上，得到当前值的内存地址。

4.5.2 倘若当前位置不位于最后一个桶的最后一个位置，或者当前位置的后置位 tophash 不为 emptyRest，则无需向前遍历更新 tophash 标识，直接跳转到 notLast 位置即可

			// 如果桶现在以一堆emptyOne状态结束，则将这些状态更改为emptyRest状态。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}}

4.5.3 向前遍历，将沿途的空位的 tophash 都更新为 emptySet

			// 将所有emptyOne状态更改为emptyRest状态。for {b.tophash[i] = emptyRestif i == 0 {if b == bOrig {break // 如果是初始桶的开始，则完成。}// 找到前一个桶，继续在其最后一个条目处搜索。c := bfor b = bOrig; b.overflow(t) != c; b = b.overflow(t) {}i = bucketCnt - 1} else {i--}if b.tophash[i] != emptyOne {break}}

4.5.4 如果成功删除，就将计数器减一，map为空就更换新的随机因子

notLast:// 减少计数。h.count--// 重置哈希种子，使攻击者更难重复触发哈希冲突。if h.count == 0 {h.hash0 = fastrand()}break search}

4.5.5 再次检测是否存在并发写

if h.flags&hashWriting == 0 {fatal("concurrent map writes")}// 清除正在写入标志。h.flags &^= hashWriting

4.6 遍历流程 —— mapiterinit、mapiternext

4.6.1 迭代器结构：

// 一个哈希迭代结构体。
// 如果你修改了 hiter，也要更改 cmd/compile/internal/reflectdata/reflect.go
// 和 reflect/value.go 以匹配这个结构体的布局。
type hiter struct {key         unsafe.Pointer // 必须是第一个位置。写入nil表示迭代结束（参见cmd/compile/internal/walk/range.go）。elem        unsafe.Pointer // 必须是第二个位置（参见cmd/compile/internal/walk/range.go）。t           *maptype       // 映射的类型。h           *hmap          // 指向当前映射的指针。buckets     unsafe.Pointer // 在hash_iter初始化时的桶指针。bptr        *bmap          // 当前桶的指针。overflow    *[]*bmap       // 保持hmap.buckets的溢出桶活跃。oldoverflow *[]*bmap       // 保持hmap.oldbuckets的溢出桶活跃。startBucket uintptr        // 开始迭代的桶。offset      uint8          // 迭代开始时的桶内偏移量（应足够大以容纳bucketCnt-1）。wrapped     bool           // 是否已经从桶数组的末端回到开始。B           uint8          // 桶的大小。i           uint8          // 当前迭代的索引。bucket      uintptr        // 当前桶的索引。checkBucket uintptr        // 检查桶的索引。
}

4.6.2 mapiterinit 源码：

通过取随机数的方式，决定遍历的起始桶号，以及起始 key-value 对索引号.

// mapiterinit 初始化用于遍历映射的 hiter 结构体。
// 'it' 指向的 hiter 结构体由编译器的 order pass 在栈上分配，
// 或者由 reflect_mapiterinit 在堆上分配。
// 由于结构体包含指针，所以两者都需要将 hiter 清零。
func mapiterinit(t *maptype, h *hmap, it *hiter) {// 如果启用了竞态检测并且映射不为空，则读取映射。if raceenabled && h != nil {callerpc := getcallerpc()racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiterinit))}// 设置迭代器的映射类型。it.t = t// 如果映射为空或者计数为0，则直接返回。if h == nil || h.count == 0 {return}// 如果 hiter 结构体的大小不正确，则抛出异常。if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {throw("hash_iter size incorrect") // 参见 cmd/compile/internal/reflectdata/reflect.go}// 设置迭代器的映射指针。it.h = h// 抓取桶状态的快照。it.B = h.Bit.buckets = h.buckets// 如果桶中的指针字节为0，则分配当前切片并记住当前和旧的指针。// 这样即使在我们迭代时表增长和/或向表中添加溢出桶，也能保持所有相关的溢出桶活跃。if t.Bucket.PtrBytes == 0 {h.createOverflow()it.overflow = h.extra.overflowit.oldoverflow = h.extra.oldoverflow}// 决定从哪里开始。var r uintptr// 根据 B 的值选择随机数生成函数。if h.B > 31-bucketCntBits {r = uintptr(fastrand64())} else {r = uintptr(fastrand())}// 计算开始的桶索引。it.startBucket = r & bucketMask(h.B)// 计算迭代开始时的桶内偏移量。it.offset = uint8(r >> h.B & (bucketCnt - 1))// 设置迭代器状态。it.bucket = it.startBucket// 记住我们有一个迭代器。// 可以与另一个 mapiterinit() 并发运行。if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {atomic.Or8(&h.flags, iterator|oldIterator)}// 开始迭代的下一个元素。mapiternext(it)
}

主要代码如下：

  var r uintptrr = uintptr(fastrand())it.startBucket = r & bucketMask(h.B)it.offset = uint8(r >> h.B & (bucketCnt - 1))// iterator stateit.bucket = it.startB

• 使用 r（一个随机数）和 bucketMask(h.B)（一个基于映射大小的掩码）进行按位与操作，以确定迭代器开始时的桶索引。
• 将 r 向右移动 h.B 位，相当于除以 2^h.B（因为 h.B 是桶的数量的对数）
• 与 bucketCnt - 1 进行按位与操作,以确定桶内的偏移量
• 完成迭代器 hiter 中各项参数的初始化后，步入 mapiternext 方法开启遍历

4.6.3 mapiternext 源码：

func mapiternext(it *hiter) {h := it.h// 如果启用了竞态检测，则读取映射。if raceenabled {callerpc := getcallerpc()racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiternext))}// 如果映射正在写入，则抛出致命错误。if h.flags&hashWriting != 0 {fatal("concurrent map iteration and map write")}t := it.tbucket := it.bucketb := it.bptri := it.icheckBucket := it.checkBucketnext:// 如果当前桶为空，则处理迭代结束或映射增长的情况。if b == nil {// 如果已经遍历完所有桶，则结束迭代。if bucket == it.startBucket && it.wrapped {it.key = nilit.elem = nilreturn}// 如果映射正在增长，则处理旧桶的迁移。if h.growing() && it.B == h.B {oldbucket := bucket & it.h.oldbucketmask()b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))if !evacuated(b) {checkBucket = bucket} else {b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))checkBucket = noCheck}} else {b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))checkBucket = noCheck}// 移动到下一个桶。bucket++if bucket == bucketShift(it.B) {bucket = 0it.wrapped = true}i = 0}// 遍历桶中的条目。for ; i < bucketCnt; i++ {offi := (i + it.offset) & (bucketCnt - 1)// 跳过空条目。if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {continue}// 获取键和值的地址。k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize))if t.IndirectKey() {k = *((*unsafe.Pointer)(k))}e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize))// 处理增长期间的特殊情况。if checkBucket != noCheck && !h.sameSizeGrow() {if t.ReflexiveKey() || t.Key.Equal(k, k) {hash := t.Hasher(k, uintptr(h.hash0))if hash&bucketMask(it.B) != checkBucket {continue}} else {if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {continue}}}// 返回有效的数据。if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||!(t.ReflexiveKey() || t.Key.Equal(k, k)) {it.key = kif t.IndirectElem() {e = *((*unsafe.Pointer)(e))}it.elem = e} else {// 如果键已被删除、更新或重新插入，则检查当前哈希表。rk, re := mapaccessK(t, h, k)if rk == nil {continue // 键已被删除。}it.key = rkit.elem = re}// 更新迭代器状态。it.bucket = bucketif it.bptr != b {it.bptr = b}it.i = i + 1it.checkBucket = checkBucketreturn}// 处理溢出桶。b = b.overflow(t)i = 0goto next
}

• 利用next 和go next实现代码块循环

4.6.3.1 如果已经遍历完所有的桶，重新回到起始桶为止，则直接结束方法

 if bucket == it.startBucket && it.wrapped {it.key = nilit.elem = nilreturn}

4.6.3.2 判断map是否处于扩容流程，若桶处于旧桶数组且未完成迁移，需要将 checkBucket 置为当前的桶号。

// 如果映射正在增长，则处理旧桶的迁移。
if h.growing() && it.B == h.B {oldbucket := bucket & it.h.oldbucketmask()b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))if !evacuated(b) {checkBucket = bucket} else {b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))checkBucket = noCheck}
} else {b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))checkBucket = noCheck
}

4.6.3.3 遍历的桶号加 1，倘若来到桶数组末尾，则将桶号置为 0

bucket++
if bucket == bucketShift(it.B) {bucket = 0it.wrapped = true
}
i = 0

4.6.3.4 执行 mapaccessK 方法，基于读流程方法获取 key-value 对，通过迭代 hiter 的 key、value 指针进行接收，用于对用户的遍历操作进行响应：

rk, re := mapaccessK(t, h, k)
if rk == nil {continue // key has been deleted
}
it.key = rk
it.elem = re

这篇关于深度解析GoLand map原理及实现，手撕源码！（二）——写入、删除、遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---