Go数据结构之映射map方式
目录
- 1 map的使用
- 1.1 map基本使用
- 1.2 map注意事项
- 2 map的底层数据结构
- 2.1 bmap
- 2.2 hmap
- 3 map实现源码
- 3.1 map的初始化
- 3.2 map的赋值
- 3.3 map的查找
- 3.4 map的扩容
- 3.4.1 hashGrow函数
- 3.4.3 evacuate函数
- 3.5 map的删除
- 3.6 map的遍历
- 3.6.1 hiter结构体
- 3.6.2 mapiternext函数
- 总结
Map作为Go原生支持的另一个主要的数据结构，其使用频繁程度与切片有过之而无不及。用一句话描述map：存储键-值对映射关系的无序数据结构，保证键的唯一性但不保证并发操作安全。
本文将介绍map的基本使用以及go 1.16版本其底层实现。
1 map的使用
1.1 map基本使用
声明/初始化，一般有如下三种方式，
- 使用var声明一个map变量，需要指定键值对分别的类型，这种方式仅仅只是声明，返回的是一个nil map，既没有分配内存，无法对其进行写入操作。如果要对其进行写入操作，则还需要为其分配内存。
- 比较常用的是直接使用make初始化，在初始化map类型时，可以传一个容量（通常是不传这个参数，因为map底层有自动扩容机制，且无法准确预估map所需的容量）。
- 第三种方式就是直接在定义的同时，对map进行写入操作，这种方式适用于确定部分需要写入map的场景
// 声明一个map变量，键是string类型，值是int类型
// 但此时m还是一个nil map，无法对其进行写入
var m map[string]int
m["1"] = 1 // 报错，nil map无法写入
m = make(map[string]int) // 使用make为map分配内存，此时可以正常写入
// 可以将声明和分配内存合二为一，直接使用make函数为map分配内存
// make函数第一个参数是map的类型，第二个参数可选，表示map的容量大小
m1 := make(map[string]int)
// 第三种方式就是在定义的时候，连带着给map进行赋值
m2 := map[string]int{
"1": 1,
"2": 2,
}
赋值，其实就比较简单，直接将键放入中括号，对应的值放在等号右边即可，如果键之间存在，则实现更新；不存在，则实现插入。这里需要特别注意的是
- 对于nil map无法进行赋值操作，如果对nil map进行赋值，则会panic。
- map中的value是不可寻址的，无法直接通过map值进行更新操作，但有两种例外，1）value为int类型，编译器会通过语法糖进行直接更新；2）value为指针类型时，也能直接通过map值进行更新操作。
m := make(map[string]int)
m["1"] = 1
type Person struct {
name string
age int
}
m1 := map[string]Person{}
m1["Tom"].age++ // 错误，因为map的值是无法寻址的，这种情况需要接受旧值，将修改完后的值重新赋值
m2 := map[string]*Person{}
m2["Tom"].age++ // 正确，这种情况下没有改变map中的value，而是通过指针找到对应存储的值进行修改
- 查找，map对于查询的处理原则就是，如果key不存在，则返回value对应的零值（nil map也能进行查找，只是对于所有的查询都返回value类型零值）。如果需要判断key是否存在，则推荐使用v, ok := m["1"]的写法，ok为true表示key存在于map中。
var m map[string]int
fmt.Println(m["1"]) // nil map可以进行查找，返回的是value的默认零值
// 如果需要判断key是否存在于map中，则可以使用如下写法
if _, ok := m["1"]; ok {
fmt.Println("key存在")
} else {
fmt.Println("key不存在")
}
- 删除，主要通过调用delete函数实现map中键值对的删除操作，对于nil map也能执行删除操作，如果待删除的key不存在，则不做任何处理。
var m map[string]int delete(m ,"1")
- 遍历，只能通过for range进行map的遍历操作，而且遍历是无序的，每次遍历结果都不一样，这样做：一是为了让使用者不依赖于map的遍历顺序，二也是与map的底层实现有很大关系。实际开发过程中，如果要确定的遍历顺序，往往需要借助切片保存顺序，然后通过遍历切片去map中取值。
m := map[string]int{
"1": 1,
"2": 2,
}
// 无序遍历，每次遍历的顺序都不一样
for k, v := range m {
fmt.Println(k, v)
}
1.2 map注意事项
map是一种引用传递类型，其作为函数参数进行传递时，函数内部修改会直接影响调用者。
map遍历是无序的，即每次遍历的结果都不一样，可能是Go的设计者不想使用者依赖与map的遍历顺序性，个人认为这个也是与其底层实现有关，如果要保证有序，则需要维护额外的数据结构，与Go极简的设计原则不符。
map的key必须是支持==、!=运算的数据类型（map的key可以为float类型、chan类型自定义结构体，但不能是func、map、slice，value则可以为任意数据类型）。
因内存访问安全和哈希算法等缘故，字典被设置成“not addressable”，故不能直接修改value的值（实际上就是不允许直接修改map中的值）。如果需要对value进行修改，一般将需要将整个value返回，修改后再重新赋值，或直接将value设置成指针类型（指针能修改的原因是，通过指针修改原结构体中的数据，但没有修改map中保存的数据）。但是，如果map的value为int，那么可以直接修改value，例如：
m := map[string]int{"test":1}
m["test"]++ // 实际上是语法糖
/*
temp := m["test"]
temp += 1
m["test"] = temp
*/
map并不是多线程读写安全的，在多线程开发中使用map需要特别小心，解决此问题一般可以使用sync.RWMutex进行保护或直接使用sync.Map。
访问不存在的主键，返回对应key的零值，并不会panic。删除不存在的键值，也不会引发错误。
可对nil的字典进行读、删除操作，但是写会引发panic！即，从nil的字典中，读出来的都是value的默认值；对nil字典进行删除操作，实际不会产生任何效果。
2 map的底层数据结构
在Go 1.16版本中，使用了hash table来实现map（Go 1.24版本已经使用Swiss table作为map的底层实现，后续有空研究下），其底层实现主要借助hmap、bmap，下面详细介绍下这两个数据。
2.1 bmap
bmap是Go map中bucket的抽象，为提高存储效率，每一个 bmap 都能存储 8 个键值对。
当哈希表中存储的数据过多，单个桶已经装满时就会使用 extra.nextOverflow 中桶存储溢出的数据。上述两种不同的桶在内存中是连续存储的，我们在这里将它们分别称为正常桶和溢出桶。
bucket的结构体 bmap 在 Go 语言源代码中的定义只包含一个简单的 tophash 字段，tophash 存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能。在运行期间，bmap 结构体其实不止包含 tophash 字段，因为哈希表中可能存储不同类型的键值对，而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。runtime.bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段，不过我们能根据编译期间的 cmd/compile/internal/gc.bmap 函数重建它的结构：
type bmap struct {
tophash [bucketCnt]uint8
}
// 利用../go/src/cmd/compile/internal/gc/reflect.go文件中的bmap函数反推
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
overflow uintptr
}
桶和溢出桶
- 桶（bucket）: 每个桶包含固定数量的键值对，Go 中每个桶默认可以存储 8 对键值对。
- 溢出桶（overflow bucket）: 当一个桶已满但仍需插入新的键值对时，会创建一个新的桶作为当前桶的溢出桶。
溢出桶的作用
解决哈希冲突:
- 在理想情况下，每个键会被分配到不同的桶中。然而，在实际应用中，由于哈希函数的特性，多个键可能会被分配到同一个桶中（即哈希冲突）。
- 当一个桶已满且仍然需要存储新的键值对时，Go 会创建一个新的桶作为当前桶的溢出桶，并将新键值对存储在这个溢出桶中。
管理存储空间:
- 溢出桶允许动态扩展 map 的存储容量。通过使用链表结构（由多个溢出桶组成），可以有效地管理超过初始桶容量的数据。
- 这种机制避免了频繁地重新分配和复制整个哈希表，从而提高了性能。
高效查找:
- 即使存在多个溢出桶，Go 的
map实现仍然能够高效地进行键值对的查找。通过遍历主桶及其关联的溢出桶，可以快速找到所需的键值对。 - 溢出桶的设计确保了查找操作在平均情况下仍然是 O(1) 时间复杂度。
2.2 hmap
hmap是Go实现map的底层数据结构，主要用于管理bucket的扩容、元素的查找/删除等，其具体结构如下：
type hmap struct {
count int // 元素个数，调用 len(map) 时，直接返回此值
flags uint8 // 标记，对应 const 中 '// flags' 下的几个状态
B uint8 // buckets 的对数 log_2
noverflow uint16 // overflow 的 bucket 近似数
hash0 uint32 // 计算 key 的哈希的时候会传入哈希函数
buckets unsafe.Pointer // 指向 buckets 数组，大小为 2^B。如果元素个数为0，就为 nil
// 扩容的时候，buckets 长度会是 oldbuckets 的两倍
oldbuckets unsafe.Pointer // 指向扩容前的数组（渐进式扩容）
nevacuate uintptr // 指示扩容进度，小于此地址的 buckets 迁移完成
extra *mapextra //保存溢出桶的信息
}
type mapextra struct {
// 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
// 使用 extra 来存储 overflow bucket，这样可以避免 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
overflow *[]*bmap // overflow 包含的是 hmap.buckets 的 overflow 的 bucket
oldoverflow *[]*bmap // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
nextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}
3 map实现源码
3.1 map的初始化
使用make函数创建map：
make(map[k]v, hint)
在 hint <= 8(键值对的个数) 时，会调用 makemap_small 来进行初始化，如果 hint > 8，则调用 makemap。在预估待插入的元素个数小于8或者需要的bucket为0时，Go编译器会采用延迟分配策略，只有在真正往map中写入数据时， 才会分配bucket。
makemap函数主要流程如下：
- 内存安全检查：通过计算预估内存 = 元素数量(hint) × 单个桶大小(t.bucket.size)，防止内存溢出攻击和无效分配，若检测失败，将 hint 重置为 0（后续按最小分配处理）
- 初始化 hmap 结构体：若传入
h为 nil，新建hmap结构（map 的底层表示）；随后h.hash0 = fastrand()：生成随机哈希种子，用于增加哈希随机性，防止哈希碰撞攻击，相同 key 在不同 map 中产生不同哈希值 - 计算桶数量指数 B：根据负载因子确定合适的桶数量（
2^B个桶），循环增加B直到满足：6.5 * 2^B >= hint - 分配桶数组：若
B == 0（hint=0），延后到首次写入时分配；其他情况，调用makeBucketArray分配主桶数组（长度为2^B），如果 B >= 4 额外预分配溢出桶（减少运行时分配开销，这里也说明正常桶与溢出桶是内存地址连续的数组） - 溢出桶管理：若存在预分配溢出桶（
nextOverflow != nil），初始化h.extra结构，记录可用溢出桶链表。最后一个溢出桶的overflow指针会指向第一个正常桶，以此形成一个环。
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 进行内存大小的检查，如果溢出或者内存超出最大内存空间，将hint（元素个数）设置为0
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
// 初始化 Hmap，即如果当前Hamp为空，则new hmap
// 设置map的哈希计算种子随机数hash0
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
// 按照提供的元素个数，根据负载因子计算合理的 B 值，以确保 6.5 * 2 ^ B >= hint
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
// 初始化 hash table
// 如果 B 等于 0，那么 buckets 就会在赋值（ mapassign ）的时候再分配
// 如果长度比较大，分配内存会花费长一点
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
// uintptr(1) << ( b & (sys.PtrSize*8-1)) 2^b
base := bucketShift(b)
nbuckets := base
// 当桶的数量小于2^4 时，由于数据较少、使用溢出桶的可能性较低，
// 这时就会省略创建溢出桶的过程以减少额外开销
if b >= 4 {
// 当桶的数量多于2^4时，就会额外创建 2^(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 {
// dirtyalloc was previously generated by
// the above newarray(t.bucket, int(nbuckets))
// but may not be empty.
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
memclrHASPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
// 如果创建的桶数量不等于2^b，说明分配了额外的溢出桶
if base != nbuckets {
// 2^b个桶后面就是溢出桶
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
// 取nextOverflow 里面的最后一个元素，并把最后一个buckets 的末尾偏移的指针指向空闲的bucket (目前就是第一个buckets了)
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
下图是不同B值时，初始化得到的map，如果B小于4，则编译器不会为map分配溢出桶（认为map的规模比较小，需要使用到溢出桶的概率不大）；只有在B大于等于4时，才会为map分配 2^(B-4)个溢出桶，需要注意的是正常桶与溢出桶在底层是一个内存地址连续的数组！
3.2 map的赋值
map的赋值操作核心是：通过hash函数，找到key插入到bmap数据的下标索引，然后就需要遍历该下标包含的所有bucket，寻找第一个能插入的位置或者寻找该key是否已经存在。hash值在这里的主要作用有两个：
- tophash：由于一个bucket存储了8个键值对，为了快速比较key，编译器会将hash值的前8位（64位操作系统）存储到bucket到tophash数组。
- 确定bmap的索引：hash值与map的B值进行mask操作，确定该key存储的下标位置。
赋值操作底层mapassign函数的主要流程：
1. 安全检查和初始化
- 空 map 检查：对 nil map 赋值会 panic
- 并发写检查：检测到其他 goroutine 正在写 map 时抛出异常（Go map 非并发安全）
- 哈希计算：使用类型特定的哈希函数计算键的哈希值
- 标记写操作：设置
hashWriting标志位（防止并发写） - 延迟初始化：若桶数组未分配，分配一个桶（最小化空 map 开销）
2. 定位桶和搜索键
双层循环搜索：外层遍历对应index下所有的bucket，内层循环处理每个桶的 8 个槽。
- 遍历时，需要记录第一个可以插入的位置。
- 同时，需要遍历完全插入位置下，所有的bucket。如果遇到tophash相等，进一步判断key是否一致，key也相等，则更新key的信息并结束循环。
- 遇到
emptyRest（后续全空）时，提前终止搜索。
3. 键不存在时的处理
- 扩容条件：负载因子超标（
count/(2^B) > 6.5）；溢出桶过多（noverflow >= 2^min(B, 15)）。 - 扩容后重试：桶布局改变需重新定位
- 分配新溢出桶：当所有桶都无空闲槽时，则申请一个溢出桶
4. 收尾工作
- 返回值的存储位置：调用方通过此指针写入值
- 间接值处理：若值类型为指针，返回实际值地址
/*
t *maptype：map 的类型信息
h *hmap：map 的底层结构
key unsafe.Pointer：要插入或更新的键
返回：指向值存储位置的指针（写入值需通过此指针）
*/
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 对于nil的map不能进行写操作，直接panic
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled {
msanread(key, t.key.size)
}
// 如果有别的goroutine正在写此map，即发生了并发写，直接异常退出
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
// 计算需要写入的key的hash值
hash := t.hasher(key, uintptr(h.hash0))
// 调用hasher函数时，可能发生paninc，因此没法完成一次写操作
// 如果hasher没有发生panic，那么将flags设置成flags += 4
h.flags ^= hashWriting
// 如果bucket没有被分配内存，则分配一个bucket（延迟初始化）
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// 计算低 8 位 hash，根据计算出的 bucketMask 选择对应的 bucket 编号
bucket := hash & bucketMask(h.B)
// 如果map正在扩容，则完成搬迁工作
if h.growing() {
growWork(t, h, bucket)
}
// 计算key对应桶编号的地址，以及hash值的高8位
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
top := tophash(hash)
var inserti *uint8 // 需要写入tophash数组的下标
var insertk unsafe.Pointer // 写入key的对象指针（地址）
var elem unsafe.Pointer // 写入value的对象指针（地址），即返回值
bucketloop:
// 开启双层循环，外层遍历bucket的所有overflow桶，内层遍历每个bucket的cell
// 目的：找到空的cell（key不存在），或者top所在的位置（key已存在）
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top { // 当前top不一致，继续比对下一个
// 找到第一个空的cell，并保存下表以及地址信息
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.elemsize))
}
// 此cell为空且后面也都是空cell，那么inserti必定已不为空。
// 这种情况直接退出bucket cell的遍历
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 如果b.tophash[i] == top，计算key对应的地址
// k是指针对象，解引用
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
// 如果两个 key 的首八位后最后八位哈希值一样，就会进行其值比较，算是一种哈希碰撞吧
if !t.key.equal(key, k) {
continue
}
// map已经有此key存在了，那么直接更新
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
// bucket 的 8 个槽没有满足条件的能插入或者能更新的，去 overflow 里继续找
// overflow 为 nil，说明到了 overflow 链表的末端了，退出外层循环
ovf := b.overflow(t)
if ovf == nil {
break
}
// 赋值为链表的下一个元素，继续循环
b = ovf
}
// 没有找到 key，分配新的空间
// 如果触发了最大的 load factor，或者已经有太多 overflow buckets
// 并且这个时刻没有在进行 growing 的途中，那么就开始 growing
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 {
// The current bucket and all the overflow buckets connected to it are full, allocate a new one.
// 前面在桶里找的时候，没有找到能塞这个 tophash 的位置
// 说明当前所有 buckets 都是满的，分配一个新的 bucket
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// store new key/elem at insert position
if t.indirectkey() { // 如果键的比较大，则直接使用指针存储
kmem := newobject(t.key)
// 二级指针，insertk看作是指向指针的指针
*(*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 {
throw("concurrent map writes")
}
// flags对hashWriting按位置0，'^='表示按右边hashWriting二进制为1的位置，置0
// 还原写操作之前的flags
h.flags &^= hashWriting
if t.indirectelem() {
// 如果value是个大对象，则bucket中存储的是对象地址unsafe.Pointer，取出存放value对象的地址
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
3.3 map的查找
mapAccess1、mapaccess2、mapaccessk是常用的map查找函数，三个函数的主要实现基本类似，主要区别在于函数的返回值不同。
- mapaccess1只有一个value的返回值，v := m[k]时调用，如果k不存在，返回的是value类型对应的零值
- mapaccess2返回value，bool，v, ok := m[k]时调用，如果k不存在，返回是value类型对应的零值，false
- mapaccessk返回key，value，如果k不存在，返回nil，nil
下面主要分析下mapaccess2函数的实现：
安全性检查
- 空 map 处理：如果 map 为 nil 或元素数为 0，直接返回零值和 false
- 特殊处理：如果键类型可能引发 panic（如函数类型），调用哈希函数触发 panic
- 读写冲突检测：当其他 goroutine 正在写 map 时抛出异常（Go map 非并发安全）
计算哈希和定位桶
bucketMask(h.B)：生成用于取模的掩码（如 B=3 时，mask=0b111）- 桶定位公式：桶地址 = buckets起始地址 + (hash & mask) * 桶大小
扩容期间的特殊处理：当 map 正在扩容时，数据可能存在于新旧桶中（扩容有等量扩容与双倍扩容两种，详细解释见3.4节），如果是双倍扩容，且该下标还没有迁移完成，则在老桶中查找
双层循环搜索键值对
- tophash 比较：先比较哈希高8位，快速过滤不匹配项
- emptyRest 优化：遇到标记为
emptyRest的槽位，表示后续全部为空，直接跳出循环
键值定位：
- 键位置：桶地址 + 数据偏移 + 索引 * 键大小
- 值位置：桶地址 + 数据偏移 + 8*键大小 + 索引 * 值大小
- 间接存储处理：若键或值为指针类型，需解引用获取实际数据
- 未找到处理：返回预定义的零值地址和 false
/*
t *maptype：map 的类型信息
h *hmap：map 的底层结构
key unsafe.Pointer：要查找的键
返回值：
unsafe.Pointer：指向值的指针（未找到时指向零值）
bool：表示键是否存在
*/
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapaccess2)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.key.size)
}
// 如果map为空，或者元素个数为零，直接返回零值
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0)
}
return unsafe.Pointer(&zeroVal[0]), false
}
// 读、写冲突
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 计算哈希值，并且加入 hash0 引入随机性
hash := t.hasher(key, uintptr(h.hash0))
// 如果 B = 3，那么结果用二进制表示就是 111，2^B-1
m := bucketMask(h.B)
// b 就是存储key所在的 bucket 的地址
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
// h.oldbuckets ！= nil时，说明 map 发生了扩容。这时候，新的 buckets 里可能还没有老的内容，
// 所以一定要在老的里面找，否则有可能发生“消失”的诡异现象
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 如果不是等量扩容，新bucket的数量是老bucket的两倍
m >>= 1
}
// 求出 key 在老的 map 中的 bucket 位置
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
// 如果oldb 没有搬迁到新的 bucket，那就在老的 bucket 中寻找
if !evacuated(oldb) {
b = oldb
}
}
// 计算高 8 位的 hash，相当于右移 56 位，只取高8位
top := tophash(hash)
bucketloop:
// 两层循环，第一层遍历bucket后面所有的溢出桶
// 第二层遍历每个桶内部的8个key位置
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// 如果top不匹配
if b.tophash[i] != top {
// emptyRest标记此cell后面所有的key（包括overflow桶）都为空，此时直接跳出循环
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 通过 bmap的地址+dataOffset+i*keysize 定位key的位置
dataOffset = unsafe.Offsetof(struct{
b bmap // bmap理解为[bucketCnt]uint8
v int64
}{}.v)
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() { // 如果key是指针，那么解引用
k = *((*unsafe.Pointer)(k)) // 先将k转化为*unsafe.Pointer类型，然后取出该地址存储的值
}
// 如果key相等，定位value的位置，在map中找到了key-value，然后返回
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() { // 如果value是指针，那么解引用
e = *((*unsafe.Pointer)(e))
}
return e, true
}
}
}
// 如果遍历完所有的bucket(包括溢出桶)，还没找到，则返回零值
return unsafe.Pointer(&zeroVal[0]), false
}
3.4 map的扩容
扩容是hash table中比较常见的一种操作，主要用于提高查询效率。Go map的扩容触发条件如下：
是不是已经到了 load factor 的临界点，即元素个数 >= 桶个数*6.5，这时候说明大部分的桶可能都快满了，如果插入新元素，有大概率需要挂在 overflow 的桶上。
overflow 的桶是不是太多了，
当 bucket 总数 < 2 ^ 15 时，overflow 的 bucket 总数 >= bucket 的总数
当 bucket 总数 >= 2 ^ 15 时，overflow 的 bucket >= 2 ^ 15
满足上述两种情况时，就被认为溢出桶太多了。为啥会导致这种情况呢？是因为我们对 map 一边插入，一边删除，会导致其中很多桶出现空洞，这样使得 bucket 使用率不高，值存储得比较稀疏。在查找时效率会下降。
// 装载因子超过 6.5
func overLoadFactor(count int64, B uint8) bool {
return count >= bucketCnt && float32(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
return noverflow >= uint16(1)<<(B&15)
}
针对上述两种情况，采用了不同的解决方法:
- 针对 1，将 B + 1，进而 hmap 的 bucket 数组扩容一倍；
- 针对 2，通过移动 bucket 内容，使其倾向于紧密排列从而提高 bucket 利用率（等量扩容）。
3.4.1 hashGrow函数
hashGrow函数只有在往map中新插入一个值，且需要触发扩容时才会被调用。该函数主要根据扩容条件判断需要执行哪一种扩容，然后申请新的bucket内存，更新bucket、oldbucket的信息，具体的迁移工作是由growWork 和 evacuate函数中完成的。Go map的扩容也采用的渐进式迁移，每一次赋值、删除操作时，如果map处于扩容状态，则会保证key对应的索引完全迁移（这样，后续的操作只需要在h.bucket中完成即可），同时将h.nevacuate指示的下标索引对应的所有bucket也完成迁移。
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger.
// Otherwise, there are too many overflow buckets, so keep the same number of buckets and "grow" laterally.
// 如果 load factor 超过了阈值，那么需要对 map 进行扩容，即 B = B + 1，bucket 总数会变为原来的二倍
// 如果还没到阈值，那么只需要保持相同数量的 bucket，横向拍平就行了（等量扩容）
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow // 如果flags原先的值小于sameSizeGrow，h.flags += sameSizeGrow
}
// 将原先的bucket分给oldbuckets，然后申请新的bucket内存
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
// 先把 h.flags 中 iterator 和 oldIterator 对应位清 0，然后如果发现 iterator 位为 1，那就把它转接到 oldIterator www.devze.com位，使得 oldIterator 标志位变成 1。
// 潜台词就是：buckets 现在挂到了 oldBuckets 名下了，对应的标志位也转接过去吧。
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
// 将原先的overflow搬到oldoverflow
if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
python }
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
// 如果新的bucket有overflow bucket，赋值给nextOverflow
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
// the actual copying of the hash table data is done incrementally by growWork() and evacuate().
// 实际的哈希表元素的拷贝工作是在 growWork 和 evacuate 中增量慢慢地进行的
}
3.4.3 evacuate函数
evacuate函数实现迁移的核心点在于：
evacDst结构：跟踪迁移目标位置
等量扩容：只使用 x（相同索引位置，平行迁移）
翻倍扩容：使用 x 和 y 两个目标，将原来一个索引下的bucket内容分配到新bmap数组的两个相关索引下：
x：新桶数组低位（索引 =oldbucket）y：新桶数组高位（索引 =oldbucket + newbit）
在翻倍扩容的时候，虽然键的哈希值没有变化，但通过精妙的迁移策略和新索引计算机制，仍然能确保键的正确查找！翻倍扩容时，新掩码(newbit) = 1 << B（B 是旧桶数量的指数），迁移到新桶数组到高位或地位，决定于hash & newbit。然后在查找时，使用新掩码计算索引，在不改变hash函数的情况完美解决查找问题。（新旧mask的区别就是：新mask比旧值多了 B+1 bit位的判断，后 B bit位还是保持一致，所以可以利用hash的第 B+1位值来确定key迁移到低位还是高位）
新索引 = {
旧索引 (当 hash & newbit == 0 时)
旧索引 + newbit (当 hash & newbit != 0 时)
} ======> 新索引 = hash & (newMask)，新mask的第 B+1 bit位的值 == 2^B
newMask = (1 << (B+1)) - 1 = (1 << B) * 2 - 1 = newbit*2 - 1
假设：
- 旧 B=2 (4个桶，掩码 0b11)
- 新 B=3 (8个桶，掩码 0b111)
- newbit = 1<<2 = 4 (0b100)
- 键哈希值：h = 13 (二进制 0b1101)
| 阶段 | 计算过程 | 结果 |
|---|---|---|
| 旧索引 | h & 0b11 = 0b1101 & 0b0011 | 1 (0b01) |
| 迁移决策 | h & newbit = 0b1101 & 0b0100 | 4 (非0) → 迁移到高位 |
| 新索引 | h & 0b111 = 0b1101 & 0b0111 | 5 (0b101) |
| 验证 | 旧索引(1) + newbit(4) | 5 |
// evacDst is an evacuation destination.
type evacDst struct {
b *bmap // current destination bucket
i int // key/elem index into b
k unsafe.Pointer // pointer to current key storage
e unsafe.Pointer // pointer to current elem storage
}
// 该函数用于实现hmap扩容时，数据的搬迁工作
// 如果是等量扩容，那么就初始化一个evacDst
// 如果是翻倍扩容，那么就初始化两个evacDst
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 定位旧bucket的地址以及扩容前map的容量
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
// 如果 b 没有被搬迁过
if !evacuated(b) {
// xy contains the x and y (low and high) evacuation destinations.
// xy 包含的是移动的目标
// x 表示新 bucket 数组的前(low)半部分，y 表示新 bucket 数组的后(high)半部分
var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.e = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
// Only calculate y pointers if we're growing bigger.
// Otherwise GC can see bad pointers.
// 如果不是等 size 扩容，前后 bucket 序号有变，使用 y 来进行搬迁
// 扩容后的map bucket数量是原先的两倍，x，y分别各占一半，数量与扩容前一样
// y部分桶的编号： oldbucket+newbit
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))
}
// 遍历所有的 bucket，包括 overflow buckets，b 是老的 bucket 地址
for ; b != nil; b = b.overflow(t) {
// 从oldbucket的第一个cell开始
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*uintptr(t.keysize))
// 遍历 bucket 中的所有 cell
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
// 当前 cell 的 top hash 值
top := b.tophash[i]
// 如果 cell 为空，即没有 key
if isEmpty(top) {
// 那就标志它被"搬迁"过，继续下一个cell
b.tophash[i] = evacuatedEmpty
continue
}
// 正常不会出现这种情况
// 未被搬迁的 cell 只可能是 empty 或是正常的 top hash（大于 minTopHash）
if top < http://www.devze.comminTopHash {
throw("bad map state")
}
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8
if !h.sameSizeGrow() {
// Compute hash to make our evacuation decision (whether we need
// to send this key/elem to bucket x or bucket y).
// 计算哈希，以判断我们的数据要转移到哪一部分的 bucket，
// 可能是 x 部分，也可能是 y 部分
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reFlexivekey() && !t.key.equal(k2, k2) {
// If key != key (NaNs), then the hash could be (and probably
// will be) entirely different from the old hash. Moreover,
// it isn't reproducible. Reproducibility is required in the
// presence of iterators, as our evacuation decision must
// match whatever decision the iterator made.
// Fortunately, we have the freedom to send these keys either
// way. Also, tophash is meaningless for these kinds of keys.
// We let the low bit of tophash drive the evacuation decision.
// We recompute a new random tophash for the next level so
// these keys will get evenly distributed across all buckets
// after multiple grows.
useY = top & 1
top = tophash(hash)
} else {
// 根据hash & newbit 来确定新bucket的索引，确保迁移完成之后，
// 使用原先的hash值 & 新的mask 还能找到正确的索引
if hash&newbit != 0 {
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
// 在oldbucket对应的cell中标记top的搬迁状态
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
dst := &xy[useY] // evacuation destination
// 当前bucket中已经放满了元素，需要使用overflow bucket
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 // mask dst.i as an optimization, to avoid a bounds check
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
} else {
typedmemmove(t.key, dst.k, k) // copy elem
}
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
dst.i++
// These updates might push these pointers past the end of the
// key or elem arrays. That's ok, as we have the overflow pointer
// at the end of the bucket to protect against pointing past the
// end of the bucket.
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// Unlink the overflow buckets & clear key/elem to help GC.
// 如果没有协程在使用老的 buckets，就把老 buckets 清除掉，帮助gc
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// Preserve b.tophash because the evacuation state is maintained there.
// 只清除bucket 的 key,value 部分，保留 top hash 部分，指示搬迁状态
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n)
}
}
// 更新搬迁进度，如果此次搬迁的 bucket 等于当前进度
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
3.5 map的删除
map的删除主要流程就是需要在key所在的索引bmap链表中查找到对应的值，进行内容的删除释放。这里需要特别注意的是，为了提升查找效率，有一个emptyRest前向传播机制：如果被删除的key后续位置都是emptyRest，则需要将其前面标记为emptyOne的cell升级为emptyRest，表示从这个cell往后不再有数据。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapdelete)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil{
msanread(key, t.key.size)
}
// 如果map为空，或者元素个数为零，直接返回
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0)
}
return
}
// 有goroutine在写map时，无法完成删除操作
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
// 计算需要写入的key的hash值
hash := t.hasher(key, uintptr(h.hash0))
// 调用hasher函数时，可能发生paninc，因此没法完成一次写操作
// 如果hasher没有发生panic，那么将flags设置成flags += 4
h.flags ^= hashWriting
// 计算低 8 位 hash，根据计算出的 bucketMask 选择对应的 bucket 编号
bucket := hash & bucketMask(h.B)
// 如果map正在扩容，则完成搬迁工作
if h.growing() {
growWork(t, h, bucket)
}
// 计算key对应桶编号的地址，以及hash值的高8位
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
// 两层循环，第一层遍历bucket后面所有的溢出桶
// 第二层遍历每个桶内部的8个key位置
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// 如果top不匹配
if b.tophash[i] != top {
// emptyRest标记此cell后面所有的key（包括overflow桶）都为空，此时直接跳出循环
if b.tophash[i] == emptyRest {
break search
}
continue
}
// 如果b.tophash[i] == top，计算key对应的地址
// k是指针对象，解引用
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 为了保存key的原始类型，便于后续的清理
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
// 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
// 如果两个 key 的首八位后最后八位哈希值一样，就会进行其值比较，算是一种哈希碰撞
if !t.key.equal(key, k2) {
continue
}
// Only clear key if there are pointers in it.
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)
}
// 标记tophash的状态
b.tophash[i] = emptyOne
// If the bucket now ends in a bunch of emptyOne states, change those to emptyRest states.
// It would be nice to make this a separate function, but for loops are not currently inlineable.
if i == bucketCnt-1 { // 删除的key位于bucket的尾巴
// 如果后续还有overflow桶，且桶内部还有元素，那么直接跳到notLast
// 将此tophash标记为emptyOne即可
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
// 如果key不是最后一个，且后续cell还有元素，也直接跳到notLast
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
for {
// 删除的key后面不再有元素，需要将tophash标记为emptyRest
// 同时往前寻找，并将前面tophash为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
// 从key的bucket开始，查找当前bucket的前一个桶地址
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
// bucket内部从最后一个cell开始查找tophash为emptyOne的cell
i = bucketCnt - 1
} else {
i--
}
// 查找到一个有内容的tophash，结束循环
if b.tophash[i] != emptyOne {
break
}
}
notLast:
h.count--
// Reset the hash seed to make it more difficult for attackers to
// repeatedly trigger hash collisions. See issue 25237.
if h.count == 0 {
h.hash0 = fastrand()
}
break search
}
}
// 禁止并发写
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
// flags对hashWriting按位置0，
// '^='表示按右边hashWriting二进制为1的位置，置0，其他位置与flags保持一致
// 还原写操作之前的flags
h.flags &编程客栈^= hashWriting
}
3.6 map的遍历
3.6.1 hiter结构体
在对map进行遍历时，会借助迭代器hiter辅助完成整个map的循环遍历，其中startBucket标记此次遍历的起始位置，wrapped标记遍历是否从头开始，checkBucket则是用于扩容中进行遍历时，坚持oldBucket中的数据。
type hiter struct {
// key 指针，保存此次遍历得到的key
key unsafe.Pointer
// value 指针，保存此次遍历得到的value
value unsafe.Pointer
// map 类型，包含如 key size 大小等
t *maptype
// map header
h *hmap
// 初始化时指向的 bucket
buckets unsafe.Pointer
// 当前遍历到的 bmap
bptr *bmap
overflow [2]*[]*bmap
// 起始遍历的 bucet 编号
startBucket uintptr
// 遍历开始时 cell 的编号（每个 bucket 中有 8 个 cell）
offset uint8
// 是否从头遍历了
wrapped bool
// B 的大小
B uint8
// 指示当前 cell 序号
i uint8
// 指向当前的 bucket
bucket uintptr
// 因为扩容，需要检查的 bucket
checkBucket uintptr
}
3.6.2 mapiternext函数
对map进行遍历时，首先会调用mapiterinit函数，初始化hiter，该函数逻辑比较简单，主要就是随机确定遍历起始位置，这里的起始位置包括：bmap的数组的起始下标、bmap bucket内部cell的起始点。随后调用mapiternext函数开始执行具体的遍历操作（每调用一次mapiternext函数获取一个map中的键值对），该过程的主要流程如下：
1. 首先检查是否有并发写操作，如果有则抛出异常。
2. 获取迭代器当前的状态（当前遍历的bucket，当前bucket内的位置i，当前bucket指针b等）。
3. 如果当前bucket（b）为nil，说明需要处理下一个bucket或者已经遍历完一圈。
- 如果当前bucket序号（bucket）等于起始bucket（it.startBucket）且已经标记为绕回（wrapped），说明已经遍历完所有bucket，设置key和elem为nil并返回。
- 如果map正在扩容且迭代器开始时的B（it.B）等于当前map的B（h.B），说明迭代开始后扩容未完成，需要处理旧桶：
- 计算对应的旧桶（oldbucket）地址。
- 如果该旧桶尚未迁移（evacuated），则设置checkBucket为当前bucket（用于后续判断键是否属于当前新桶），并继续遍历旧桶。
- 如果已经迁移，则直接遍历新桶中对应位置的桶，并将checkBucket设置为noCheck。
- 否则，直接遍历新桶中当前bucket位置的桶。
- 然后bucket序号加1，如果达到bucket总数（2^B），则重置为0并标记wrapped为true（表示已经绕回一圈）。
- 重置i为0，开始遍历新桶。
4. 遍历当前bucket（b）的8个cell（槽位），注意这里不是从0开始，而是根据it.offset进行偏移（使用offi = (i+it.offset) & (bucketCnt-1)）以实现随机开始。
- 如果tophash[offi]为空（emptyOne或evacuatedEmpty）则跳过。
- 获取键k和值e的地址。
- 如果checkBucket不为noCheck（说明在扩容过程中且当前遍历的是旧桶），则需要判断该键是否属于当前迭代的新桶（checkBucket）：
- 对于正常键（非NaN），计算其哈希值并判断它是否属于checkBucket，如果不属于则跳过。
- 对于NaN（k!=k），使用tophash的低位来决定它应该去哪个桶，如果与checkBucket的高位不匹配则跳过。
- 如果键值有效，则判断该槽位是否已经被迁移（evacuatedX或evacuatedY）且键是正常的（可比较且相等）：
- 如果未被迁移，或者键是NaN（不可比较），则直接使用当前找到的键值对（因为此时数据还未迁移或无法比较，所以认为有效）。
- 否则，说明在迭代过程中map已经扩容完成，该键可能已经被迁移，需要从新map中查找（调用mapaccessK）：如果返回的键为nil，说明该键已被删除，跳过；否则使用返回的键值对。
5. 设置迭代器的状态（key, elem, bucket, bptr, i, checkBucket）并返回。
6. 如果当前bucket的8个cell都遍历完了，则跳到overflow bucket（如果有），重置i为0，然后跳转到next标签继续处理。
func mapiternext(it *hiter) {
h := it.h
if raceenabled {
callerpc := getcallerpc()
racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
}
// 如果有goroutine正在写，抛出异常
if h.flags&hashWriting != 0 {
throw("concurrent map iteration and writes")
}
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket
next:
// 后续没有overflow bucket需要遍历
if b == nil {
// 当前遍历的bucket=startBucket，即完成循环回到最初的位置
// 且该bucket已经从头到尾遍历完了，map的遍历结束
if bucket == it.startBucket && it.wrapped {
// end of iteration
it.key = nil
it.elem = nil
return
}
// 如果map正处于扩容状态，还需要遍历oldbucket
if h.growing() && it.B == h.B {
// Iterator was started in the middle of a grow, and the grow isn't done yet.
// If the bucket we're looking at hasn't been filled in yet (i.e. the old
// bucket hasn't been evacuated) then we need to iterate through the old
// bucket and only return the ones that will be migrated to this bucket.
oldbucket := bucket & it.h.oldbucketmask()
// 根据bucket num在oldbucket的编号位置，计算bucket的地址
b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
if !evacuated(b) {
// 如果oldbucket中此编号的bucket没有完成搬迁，那么标记check
checkBucket = bucket
} else {
// 如果oldbucket中此编号的bucket完成了搬迁，直接遍历newbucket中对应位置的bucket
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
} else {
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
// 指向下一个bucket
bucket++
// 判断是否已经遍历到了末尾，如果是，则需要从头重新开始遍历，
// 直至bucket == startbucket，标记一次完整的遍历
if bucket == bucketShift(it.B) {
bucket = 0
it.wrapped = true
}
i = 0
}
// 遍历bucket的8个cell，但不是从头开始遍历的
for ; i < bucketCnt; i++ {
offi := (i + it.offset) & (bucketCnt - 1)
// 如果tophash为空，即没有数据，直接检查下一个
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
// TODO: emptyRest is hard to use here, as we start iterating
// in the middle of a bucket. It's feasible, just tricky.
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.elemsize))
if checkBucket != noCheck && !h.sameSizeGrow() {
// Special case: iterator was started during a grow to a larger size
// and the grow is not done yet. We're working on a bucket whose
// oldbucket has not been evacuated yet. Or at least, it wasn't
// evacuated when we started the bucket. So we're iterating
// through the oldbucket, skipping any keys that will go
// to the other new bucket (each oldbucket expands to two buckets during a grow).
if t.reflexivekey() || t.key.equal(k, k) {
// If the item in the oldbucket is not destined for the current new bucket in the iteration, skip it.
hash := t.hasher(k, uintptr(h.hash0))
if hash&bucketMask(it.B) != checkBucket {
continue
}
} else {
// Hash isn't repeatable if k != k (NaNs). We need a
// repeatable and randomish choice of which direction
// to send NaNs during evacuation. We'll use the low
// bit of tophash to decide w编程客栈hich way NaNs go.
// NOTE: this case is why we need two evacuate tophash
// values, evacuatedX and evacuatedY, that differ in their low bit.
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)) {
// This is the golden data, we can return it.
// OR
// key!=key, so the entry can't be deleted or updated, so we can just return it.
// That's lucky for us because when key!=key we can't look it up successfully.
it.key = k
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
it.elem = e
} else {
// The hash table has grown since the iterator was started.
// The golden data for this key is now somewhere else.
// Check the current hash table for the data.
// This code handles the case where the key has been deleted, updated, or deleted and reinserted.
// NOTE: we need to regrab the key as it has potentially been
// updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
rk, re := mapaccessK(t, h, k)
if rk == nil {
continue // key has been deleted
}
it.key = rk
it.elem = re
}
it.bucket = bucket
if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
it.bptr = b
}
it.i = i + 1
it.checkBucket = checkBucket
return
}
// 通过it.i走到此处，遍历overflow bucket
b = b.overflow(t)
i = 0
goto next
}
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程客栈(www.devze.com)。
加载中,请稍侯......
精彩评论