// for key, val := range hash {} 这种写法的展开:
ha := a
hit := hiter(n.Type)
th := hit.Type
mapiterinit(typename(t), ha, &hit) // 遍历开始
for ; hit.key != nil; mapiternext(&hit) {
key := *hit.key
val := *hit.val
}
func mapiterinit(t *maptype, h *hmap, it *hiter) {
it.t = t
it.h = h
it.B = h.B
it.buckets = h.buckets
r := uintptr(fastrand()) // 随机数
it.startBucket = r & bucketMask(h.B) // 随机数 % 2^B 作为起点桶下标
it.offset = uint8(r >> h.B & (bucketCnt - 1))
it.bucket = it.startBucket
mapiternext(it) // 遍历
}
2.2.1 桶的选择
这步主要做两件事:
在待遍历的桶为空时,定位到下一个要遍历的桶;
遍历一轮,回到起始位置后,中止遍历
func mapiternext(it *hiter) {
h := it.h
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
alg := t.key.alg
next:
if b == nil {
if bucket == it.startBucket && it.wrapped { // 遍历一轮,回到起始位置后,中止遍历
it.key = nil
it.value = nil
return
}
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) // 下一个要遍历的桶地址
bucket++ // 下一个要遍历的桶下标
if bucket == bucketShift(it.B) { // 下标到边界时,重置为0,从头开始遍历
bucket = 0
it.wrapped = true
}
i = 0
}
2.2.2 桶内元素遍历
for ; i < bucketCnt; i++ { // bucketCnt=8
offi := (i + it.offset) & (bucketCnt - 1)
k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) // 遍历8个kv
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
!(t.reflexivekey() || alg.equal(k, k)) {
it.key = k
it.value = v
} else { // 如果处于扩容期间,调用 mapaccessK 遍历旧桶
rk, rv := mapaccessK(t, h, k)
it.key = rk
it.value = rv
}
it.bucket = bucket
it.i = i + 1
return
}
b = b.overflow(t) // 遍历溢出桶
i = 0
goto next
}
2.3 字符串
遍历字符串的过程与数组、切片和哈希表非常相似,只是在遍历时会获取字符串中索引对应的字节并将字节转换成 rune。我们在遍历字符串时拿到的值都是 rune 类型的变量,for i, r := range s {} 的结构都会被转换成如下所示的形式: