前言
本文内容承接前文:深度解析GoLand map原理及实现,手撕源码!(一)——基本介绍,初始化,读
建议先阅读前文哦~
4.4 写入流程 —— mapassign
写流程主要分为以下步骤:
- 对key取hash值,再对桶数取模,确定所在的桶
- 如果当前map处于扩容状态,采用渐进扩容,迁移命中的桶
- 沿着桶链表遍历各个桶内的键值对
- 如果命中key,就对value进行更新
- 如果key不存在,就插入此键值对
- 检查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 ^= hashWriting
if 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 *uint8
var insertk unsafe.Pointer
var 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/elem
if t.IndirectKey() {
kmem := newobject(t.Key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.IndirectElem() {
vmem := newobject(t.Elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.Key, insertk, key)
*inserti = top
h.count++
done:
if h.flags&hashWriting == 0 {
fatal("concurrent map writes") // 并发的map写入
}
h.flags &^= hashWriting
if 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/elem
if t.IndirectKey() {
kmem := newobject(t.Key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.IndirectElem() {
vmem := newobject(t.Elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.Key, insertk, key)
*inserti = top
h.count++
4.4.17 再次进行并发检测,抹除写标记
done:
if h.flags&hashWriting == 0 {
fatal("concurrent map writes") // 并发的map写入
}
h.flags &^= hashWriting
if t.IndirectElem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
4.5 删除 —— mapdelete
删除主要有以下几个步骤:
- 对key取hash并取余,找到所在的桶
- 判断map是否处于扩容状态,帮助渐进扩容
- 遍历当前桶的键值对,命中就删除,并更新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 := k
if 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] = emptyRest
if i == 0 {
if b == bOrig {
break // 如果是初始桶的开始,则完成。
}
// 找到前一个桶,继续在其最后一个条目处搜索。
c := b
for 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] = emptyRest
if i == 0 {
if b == bOrig {
break // 如果是初始桶的开始,则完成。
}
// 找到前一个桶,继续在其最后一个条目处搜索。
c := b
for 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.B
it.buckets = h.buckets
// 如果桶中的指针字节为0,则分配当前切片并记住当前和旧的指针。
// 这样即使在我们迭代时表增长和/或向表中添加溢出桶,也能保持所有相关的溢出桶活跃。
if t.Bucket.PtrBytes == 0 {
h.createOverflow()
it.overflow = h.extra.overflow
it.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 uintptr
r = uintptr(fastrand())
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))
// iterator state
it.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.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket
next:
// 如果当前桶为空,则处理迭代结束或映射增长的情况。
if b == nil {
// 如果已经遍历完所有桶,则结束迭代。
if bucket == it.startBucket && it.wrapped {
it.key = nil
it.elem = nil
return
}
// 如果映射正在增长,则处理旧桶的迁移。
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 = 0
it.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 = k
if t.IndirectElem() {
e = *((*unsafe.Pointer)(e))
}
it.elem = e
} else {
// 如果键已被删除、更新或重新插入,则检查当前哈希表。
rk, re := mapaccessK(t, h, k)
if rk == nil {
continue // 键已被删除。
}
it.key = rk
it.elem = re
}
// 更新迭代器状态。
it.bucket = bucket
if it.bptr != b {
it.bptr = b
}
it.i = i + 1
it.checkBucket = checkBucket
return
}
// 处理溢出桶。
b = b.overflow(t)
i = 0
goto next
}
- 利用next 和go next实现代码块循环
4.6.3.1 如果已经遍历完所有的桶,重新回到起始桶为止,则直接结束方法
if bucket == it.startBucket && it.wrapped {
it.key = nil
it.elem = nil
return
}
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 = 0
it.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