Go map 源码理解

delete(myMap,5)

fatal("concurrent map read and map write")
fatal("concurrent map writes")

type hmap struct {
    count     int  map //中的 key-value 总数；
    flags     uint8 map //用每一位做状态标识，可以标识出 map 是否被 goroutine 并发读写、是不是正在扩容等. 全文搜索 h.flags可以看到用法很好理解。
    B         uint8   //桶数组长度的指数，桶数组长度为 2^B；
    noverflow uint16  //map 中溢出桶的数量；
    hash0     uint32  //hash 随机因子，生成 key 的 hash 值时会使用到；
    buckets    unsafe.Pointer  //桶数组；
    oldbuckets unsafe.Pointer //扩容过程中老的桶数组；
    nevacuate  uintptr    //扩容时的进度标识，index 小于 nevacuate 的桶都已经由老桶转移到新桶中；    
    extra *mapextra //预申请的溢出桶.
}

type mapextra struct {
    overflow    *[]*bmap 供桶数组 buckets 使用的溢出桶；
    oldoverflow *[]*bmap 扩容流程中，供老桶数组 oldBuckets 使用的溢出桶；


    nextOverflow *bmap 下一个可用的溢出桶.
}

const bucketCnt = 8

type bmap struct {
    // 下面是三个都是定长 8 的数组。tophash\k\v三个也是一组。
    tophash [bucketCnt]uint8
    keys [bucketCnt]T
    values [bucketCnt]T
    overflow uint8 //下一个桶指针
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
    hint 为 map 拟分配的容量；在分配前，会提前对拟分配的内存大小进行判断，倘若超限，会将 hint 置为零；
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }


    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand() 调用 fastrand，构造 hash 因子：hmap.hash0；


    B := uint8(0)
    for overLoadFactor(hint, B) {
        大致上基于 log2(B) >= hint 的思路计算桶数组的容量 B；overLoadFactor具体内容下面马上贴
        B++
    }
    h.B = B


    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) 调用 makeBucketArray 方法，初始化桶数组 hmap.buckets；
        if nextOverflow != nil {
            倘若 map 容量较大，会提前申请一批溢出桶 hmap.extra.
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }


    return 

const loadFactorNum = 13
const loadFactorDen = 2
const goarch.PtrSize = 8
const bucketCnt = 8


func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}


func bucketShift(b uint8) uintptr {
    return uintptr(1) << (b & (goarch.PtrSize*8 - 1))

makeBucketArray 会为 map 的桶数组申请内存，在桶数组的指数 b >= 4时（桶数组的容量 >= 52 ），会需要提前创建溢出桶.
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b) 记录桶数组的长度，不包含溢出桶；
    nbuckets := base 记录累加上溢出桶后，桶数组的总长度.
    if b >= 4 {
        nbuckets += bucketShift(b - 4)
    }
    
    buckets = newarray(t.bucket, int(nbuckets)) 为桶数组申请内存空间，连带着需要初始化的溢出桶：
   
    if base != nbuckets {
        //说明需要创建溢出桶，会基于地址偏移的方式，通过 nextOverflow 指向首个溢出桶的地址.
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets)) //setoverflow下面贴
    }
    return buckets, nextOverflow
}

// 倘若需要创建溢出桶，会在将最后一个溢出桶的 overflow 指针指向 buckets 数组，以此来标识申请的溢出桶已经用完.
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil || h.count == 0 {
        // 倘若 map 未初始化，或此时存在 key-value 对数量为 0，直接返回零值；
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 { 
        //  const hashWriting  = 4， 与4 就是 &100
        // 倘若发现存在其他 goroutine 在写 map，直接抛出并发读写的 fatal error；其中，并发写标记，位于 hmap.flags 的第 3 个 bit 位；
        fatal("concurrent map read and map write")
    }

    // 通过 maptype.hasher() 方法计算得到 key 的 hash 值，并对桶数组长度取模，取得对应的桶. 关于 hash 方法的内部实现，golang 并未暴露.
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)

    // 通过 hash&m 可以知道桶的位置b。其实就是取余运算。
    x % 4 => x & 3 （4是 100， 3 是 011）
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))


    if c := h.oldbuckets; c != nil {
        // 在取老桶前，会先判断 map 的扩容流程是否是增量扩容，倘若是的话，说明老桶数组的长度是新桶数组的一半，需要将桶长度值 m 除以 2.
        if !h.sameSizeGrow() {
            m >>= 1 // 除以 2
        }
        // 如果是在渐进式 hash，则要看看是不是找老 b
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) { // evacuated 会告诉你有没有迁移完
            b = oldb // 没迁移完，就从老 b 里找
        }
    }

    top := tophash(hash) //取出高 8 位. tophash具体下面会贴
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        // 外层for基于桶链表 依次遍历首个桶和后续的每个溢出桶
        for i := uintptr(0); i < bucketCnt; i++ {
            // 内层依次遍历一个桶内的 key-value 对.
            if b.tophash[i] != top {
                // 高 8 位不等于 tophash 值，可以跳过，但 go 还做了一个 tophash 判断是否删除的设计。
                if b.tophash[i] == emptyRest {
                    // 倘若不匹配且当前位置 tophash 值为 0，说明桶的后续位置都未放入过元素，当前 key 在 map 中不存在，可以直接打破循环，返回零值. 这就是上面提到的 tophash 特殊标识的用法
                    break bucketloop
                }
                continue
            }
            // 高 8 位相等。进一步比较 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，则通过地址偏移的方式取到 value
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))// 其中 dataOffset 为一个桶中 tophash 数组所占用的空间大小. 这个数字每次都是固定的。就是 x*8
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e //返回
            }
        }
    }
    // 找不到，反 0 值
    return unsafe.Pointer(&zeroVal[0])
}

func bucketMask(b uint8) uintptr {
    根据 B 求得桶数组长度 - 1 的值，用于后续的 & 运算，实现取模的效果
    return bucketShift(b) - 1
}

func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0 //const sameSizeGrow = 8 
    // 与 8 就是 => & 1000 ，其实就是看第 4 位是不是 1，flags 的每一位都有其标记
}


// 取老桶时，会调用 evacuated 方法判断数据是否已经迁移到新桶. 判断的方式是，取桶中首个 tophash 值，倘若该值为 2,3,4 中的一个，都代表数据已经完成迁移.
const emptyOne = 1
const evacuatedX = 2
const evacuatedY = 3
const evacuatedEmpty = 4 
const minTopHash = 5
func evacuated(b *bmap) bool {
    h := b.tophash[0]
    return h > emptyOne && h < minTopHash
}

// 取 key hash 值的高 8 位值 top. 倘若该值 < 5，会累加 5，以避开 0 ~ 4 的取值. 因为这几个值会用于枚举，具有一些特殊的含义.
func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (goarch.PtrSize*8 - 8))
    if top < minTopHash { //const minTopHash = 5
        top += minTopHash
    }
    return top
}

const emptyRest = 0  // 包括当前位置在内，此后的位置都为空
const emptyOne = 1  // 当前位置未放入元素


func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil {
        // 倘若 map 未初始化，直接 panic
        panic(plainError("assignment to entry in nil map"))
    }
    if h.flags&hashWriting != 0 {
        // 其他 goroutine 在进行写或删操作，抛出并发写 fatal error
        fatal("concurrent map writes")
    }
    hash := t.hasher(key, uintptr(h.hash0)) //求得 key 对应的 hash 值；


    h.flags ^= hashWriting // 异或，将 map.flags 的第 3 个 bit 位置为 1，添加写标记；


    if h.buckets == nil {
        // 还没有桶，初始化一下
        h.buckets = newobject(t.bucket) 
    }


again:
    bucket := hash & bucketMask(h.B) // 找到当前 key 对应的桶索引 bucket；bucketMask上面讲过。(模4就是&3那逻辑)
    if h.growing() {
        // 发现当前 map 正处于扩容过程，则帮助其渐进扩容。具体怎么扩容文章最后涉及
        growWork(t, h, bucket)
    }

    // 从 map 的桶数组 buckets 出发，结合桶索引和桶容量大小，进行地址偏移，获得对应桶 b；
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    top := tophash(hash) //取得 key 的高 8 位 tophash：


    var inserti *uint8 //tophash 拟插入位置
    var insertk unsafe.Pointer //key 拟插入位置 
    var elem unsafe.Pointer //val 拟插入位置
bucketloop:
//  2 层循环找位置入桶
    for {
    // 这层 for 的终止条件是内层的后面的 if ovf == nil 
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil { // isEmpty下面会贴。就是判断是不是<=1
                // <=1 说明已经找不到了。可以 break

                    // 尝试将 inserti、insertk elem 调整指向首个空位，用于后续的插入操作.
                    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))
                }
                // 能走到这，说明要么后面的元素被删了(0)，要么是空位(1)。
                // 我们还需要找到1。如果是 0 就继续continue
                if b.tophash[i] == emptyRest {
                    break bucketloop// 找到空位，这里直接 break 的是 bucketloop，注意，都不是外层 for
                }
                continue
            }
            // 能走到这，可能找到了相等的 key
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if !t.key.equal(key, k) {
                // 不等
                continue
            }
            // 更新操作
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            goto done
        }

        // 内层循环没找到，b指向下一个桶overflow，继续下一路外层for
        ovf := b.overflow(t)
        if ovf == nil {
            break // 终止外层 for
        }
        b = ovf
    }


    // 倘若没找到相等的 key，会在执行插入操作前，判断 map 是否需要开启扩容模式. 
    // 倘若需要扩容，会在开启扩容模式后，跳转回 again 标志位，重新开始桶的定位以及遍历流程.
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again 
    }


// 倘若遍历完桶链表，都没有为当前待插入的 key-value 对找到空位，则会创建一个新的溢出桶，挂载在桶链表的尾部，并将 inserti、insertk、elem 指向溢出桶的首个空位：
    if inserti == nil {
        newb := h.newoverflow(t, b) // newoverflow 具体后面会贴
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }


// 将 tophash、key、value 插入到取得空位中
    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++ // map 的 key-value 对计数器 count 值加 1；




done:
    if h.flags&hashWriting == 0 {
        // 收尾环节，再次校验是否有其他协程并发写，倘若有，则抛 fatal error. 
        fatal("concurrent map writes")
    }

    h.flags &^= hashWriting// 将 hmap.flags 中的写标记抹去
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    return //完成！
}

func isEmpty(x uint8) bool {
    return x <= emptyOne
}

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
    var ovf *bmap
    if h.extra != nil && h.extra.nextOverflow != nil {
        ovf = h.extra.nextOverflow
        if ovf.overflow(t) == nil {
            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
        } else {
            ovf.setoverflow(t, nil)
            h.extra.nextOverflow = nil
        }
    } else {
        ovf = (*bmap)(newobject(t.bucket))
    }
    h.incrnoverflow()
    if t.bucket.ptrdata == 0 {
        h.createOverflow()
        *h.extra.overflow = append(*h.extra.overflow, ovf)
    }
    b.setoverflow(t, ovf)
    return ovf
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    if h == nil || h.count == 0 {
        // 倘若 map 未初始化或者内部 key-value 对数量为 0，删除时不会报错，直接返回；
        return
    }
    if h.flags&hashWriting != 0 {
        // 倘若存在其他 goroutine 在进行写或删操作，抛出并发写的 fatal error；
        fatal("concurrent map writes")
    }


// 通过 maptype.hasher() 方法求得 key 对应的 hash 值；
    hash := t.hasher(key, uintptr(h.hash0))


    h.flags ^= hashWriting //通过异或位运算，添加写标记；


    bucket := hash & bucketMask(h.B) //找到当前 key 对应的桶索引 bucket；
    if h.growing() {
        // 倘若发现当前 map 正处于扩容过程，则帮助其渐进扩容
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    // 从 map 的桶数组 buckets 出发，结合桶索引和桶容量大小，进行地址偏移，获得对应桶 b，并赋值给 bOrg
    bOrig := b
    top := tophash(hash) //取得 key 的高 8 位 tophash
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))// 地址偏移获得现在的 k
            k2 := k
            if t.indirectkey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            if !t.key.equal(key, k2) {
                //  不相等，则继续遍历
                continue
            }

            // 则删除对应的 key-value 对
            // 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)
            }
            b.tophash[i] = emptyOne //将当前位置的 tophash 置为 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 {
                    // 倘若当前位置不位于最后一个桶的最后一个位置，或者当前位置的后置位 tophash 不为 emptyRest，则无需向前遍历更新 tophash 标识，直接跳转到 notLast 位置即可；
                    goto notLast
                }
            }
            for {
                // 向前遍历，将沿途的空位（ tophash 为 emptyOne ）的 tophash 都更新为 emptySet.
                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:
        // 倘若成功从 map 中删除了一组 key-value 对，则将 hmap 的计数器 count 值减 1. 
            h.count--
            if h.count == 0 {
                // 倘若 map 中的元素全都被删除完了，会为 map 更换一个新的随机因子 hash0.
                h.hash0 = fastrand()
            }
            break search
        }
    }


    if h.flags&hashWriting == 0 {
        // 再次校验是否有其他协程并发写，倘若有，则抛 fatal error. 
        fatal("concurrent map writes")
    }
    h.flags &^= hashWritin //将 hmap.flags 中的写标记抹去，然后退出方法.

type hiter struct {
    key         unsafe.Pointer  指向遍历得到 key 的指针；
    elem        unsafe.Pointer  指向遍历得到 value 的指针；
    t           *maptype        map 类型，包含了 key、value 类型大小等信息；
    h           *hmap           map 的指针；
    buckets     unsafe.Pointer  map 的桶数组；
    bptr        *bmap          当前遍历到的桶；
    overflow    *[]*bmap       新老桶数组对应的溢出桶；
    oldoverflow *[]*bmap       
    startBucket uintptr       遍历起始位置的桶索引； 
    offset      uint8          遍历起始位置的 key-value 对索引；
    wrapped     bool           遍历是否穿越桶数组尾端回到头部了；
    B           uint8         桶数组的长度指数；
    i           uint8         当前遍历到的 key-value 对在桶中的索引；
    bucket      uintptr        当前遍历到的桶；
    checkBucket uintptr        因为扩容流程的存在，需要额外检查的桶.
}

func mapiterinit(t *maptype, h *hmap, it *hiter) {
    it.t = t
    if h == nil || h.count == 0 {
        return
    }


    it.h = h


    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }


    // decide where to start
    // 通过取随机数的方式，决定遍历时的起始桶，以及桶中起始 key-value 对的位置。一定注意。有两个随机。
    var r uintptr
    r = uintptr(fastrand())
    it.startBucket = r & bucketMask(h.B) // startBucket 是随机的。（开始的桶位置
    it.offset = uint8(r >> h.B & (bucketCnt - 1)) // offset 也是随机的。（每个桶开始的元素位置


    // iterator state
    it.bucket = it.startBucket


    // Remember we have an iterator.
    // Can run concurrently with another mapiterinit().
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
        atomic.Or8(&h.flags, iterator|oldIterator)
    }

//完成迭代器 hiter 中各项参数的初始化后，进入 mapiternext 方法开启遍历.
    mapiternext(

func mapiternext(it *hiter) {
    h := it.h
    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.elemsize))
        if checkBucket != noCheck && !h.sameSizeGrow() {
                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 // 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
    }
    b = b.overflow(t)
    i = 0
    goto next
}