map

map是啥眉孩？怎么用？這兩個問題搞不清楚的勒葱，不用往下看了浪汪，先弄清楚再說

源碼

先看看參考資料
深度解密Go語言之 map
map筆記
Go源碼學(xué)習(xí)之map
本文源碼解析部分，會做一個全面的解析凛虽，補充上面沒說到或者沒說清楚的

創(chuàng)建

// map的數(shù)據(jù)結(jié)構(gòu)
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    // map中kv的個數(shù)死遭，可以使用len()獲取
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    // 一些標(biāo)記位
    flags     uint8
    // hash桶的數(shù)量，這里存的是次方凯旋，也就是說2^B才是桶的實際數(shù)量
    // 這么存的好處是可以通過簡單的位運算來計算mask
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    // 溢出桶的數(shù)量
    // 所謂溢出桶就是通過鏈地址法解決沖突而產(chǎn)生的桶
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    // hash隨機(jī)種子呀潭，用于生成hash隨機(jī)數(shù)
    hash0     uint32 // hash seed

    // 是一個指針钉迷，指向桶，也就是hash數(shù)組
    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    // 擴(kuò)容時用的钠署，標(biāo)記舊桶
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    // 擴(kuò)容時桶的遷移進(jìn)度標(biāo)記糠聪，標(biāo)識當(dāng)前擴(kuò)容遷移到了哪個桶
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
    // 可選
    // 用于保存指向新舊溢出桶的指針
    // 還會保存指向備用溢出桶的指針
    extra *mapextra // optional fields
}

type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    // 指向溢出桶指針切片的指針
    // 當(dāng)桶的kv都不包含指針并且是內(nèi)聯(lián)的，就不需要gc每次都掃描所有的bucket
    // 同時為了保證不讓gc干掉溢出桶谐鼎，就將指向溢出桶的指針存在overflow中
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    // 指向備用溢出桶的指針舰蟆，具體怎么用后面會說
    nextOverflow *bmap
}

// A bucket for a Go map.
// 這個是hash桶的結(jié)構(gòu)
// hmap.buckets就是指向這里
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    // 頂部hash，用于快速篩查以及做一些狀態(tài)標(biāo)記狸棍，具體后面會說到
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

// 實際編譯期間身害，bmap會經(jīng)過反射生成真正的bmap類型
// 如下是cmd/compile/internal/reflectdata/reflect.go中115行代碼
// 這里不做過多解釋
field := make([]*types.Field, 0, 5)

// The first field is: uint8 topbits[BUCKETSIZE].
arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
field = append(field, makefield("topbits", arr))

arr = types.NewArray(keytype, BUCKETSIZE)
arr.SetNoalg(true)
keys := makefield("keys", arr)
field = append(field, keys)

arr = types.NewArray(elemtype, BUCKETSIZE)
arr.SetNoalg(true)
elems := makefield("elems", arr)
field = append(field, elems)

// If keys and elems have no pointers, the map implementation
// can keep a list of overflow pointers on the side so that
// buckets can be marked as having no pointers.
// Arrange for the bucket to have no pointers by changing
// the type of the overflow field to uintptr in this case.
// See comment on hmap.overflow in runtime/map.go.
// 這里可以說下，這里會檢查kv是否會包含指針
// 如果kv沒有包含就定義為uintptr類型草戈，從而標(biāo)記桶不包含指針塌鸯，與上面說的mapextra.overflow相呼應(yīng)
// 這個之前在unsafe.Pointer的文章中說過，uintptr底層是整型非指針唐片，而且gc也不會當(dāng)做指針處理
otyp := types.Types[types.TUNSAFEPTR]
if !elemtype.HasPointers() && !keytype.HasPointers() {
    otyp = types.Types[types.TUINTPTR]
}
overflow := makefield("overflow", otyp)
field = append(field, overflow)

// 經(jīng)過上面的一頓操作丙猬，bmap的最終結(jié)構(gòu)大致就如下
// 這里注意kv的內(nèi)存布局，不是k/v/k/v這么存牵触，而是所有k連續(xù)淮悼，所有v連續(xù)，即k/k/v/v
// 這么做主要是因為go中的內(nèi)存對齊揽思，具體可看之前的文章
// 假設(shè)map[int64][int8]這種的，如果k/v/k/v這么存见擦，需要的內(nèi)存空間就會比k/k/v/v大
type bmap struct {
    // tophash
    topbits  [8]uint8
    // 存儲k
    keys     [8]keytype
    // 存儲v
    values   [8]valuetype
    // 這里是內(nèi)存空洞钉汗，主要是為了保證overflow在bmap內(nèi)存中的最后位置，具體原因后面會說到
    pad      uintptr
    // 指向下一個桶的指針
    overflow uintptr
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 判斷是否溢出
    // math.MulUintptr這里不贅述了鲤屡，看過之前源碼文章的應(yīng)該知道
    // 這里如果hint太大损痰，導(dǎo)致計算后的字節(jié)數(shù)溢出了的話，會置為0酒来，不會報panic
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }

    // new一個hmap
    if h == nil {
        h = new(hmap)
    }
    // 生成hash種子
    h.hash0 = fastrand()

    // Find the size parameter B which will hold the requested # of elements.
    // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
    // 通過hint找符合要求的最小B卢未，默認(rèn)B是0，也就是2^0=1
    // overLoadFactor用于判斷hint/2^B是否>負(fù)載因子堰汉，后面會說到
    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.
    // 如果B=0辽社，對應(yīng)的buckets內(nèi)存會延遲分配，在map寫入的時候
    if h.B != 0 {
        var nextOverflow *bmap
        // 調(diào)用makeBucketArray創(chuàng)建buckets翘鸭，具體實現(xiàn)后面會說
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        // 如果申請了備用桶內(nèi)存滴铅，nextOverflow指針指向該內(nèi)存塊
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    // 返回hmap
    return h
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
// 用于判斷hint/2^B是否>負(fù)載因子
// 這里負(fù)載因子是loadFactorNum/loadFactorDen = 13/2 = 6.5
// 即平均每個桶最多能寫入6.5對kv
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}


// makeBucketArray initializes a backing array for map buckets.
// 1<<b is the minimum number of buckets to allocate.
// dirtyalloc should either be nil or a bucket array previously
// allocated by makeBucketArray with the same t and b parameters.
// If dirtyalloc is nil a new backing array will be alloced and
// otherwise dirtyalloc will be cleared and reused as backing array.
// 構(gòu)建桶數(shù)組，其實就是分配一塊連續(xù)的內(nèi)存
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    // 計算要新建多少個桶就乓，即2^b汉匙，具體實現(xiàn)后面說
    base := bucketShift(b)
    // 把base先保存起來
    nbuckets := base
    // For small b, overflow buckets are unlikely.
    // Avoid the overhead of the calculation.
    // 如果b比較小拱烁，說明新建map的時候需求分配的長度就小，那么需要溢出桶的可能性不大
    // 這里有一個門限值噩翠，如果b >= 4即需要桶的數(shù)量 >= 16戏自，就多申請一些空間備用浦妄，需要溢出桶的可能性比較大
    // 預(yù)留分配玄呛，可以避免后續(xù)頻繁計算分配內(nèi)容，也可以減少內(nèi)存碎片
    if b >= 4 {
        // Add on the estimated number of overflow buckets
        // required to insert the median number of elements
        // used with this value of b.
        // 預(yù)留2^(b-4)個桶
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        // 計算mallocgc會分配多大的內(nèi)存塊，這里不是你申請多少就剛好分配你多少的，具體原因這里不細(xì)說，跟內(nèi)存分配有關(guān)
        up := roundupsize(sz)
        if up != sz {
            // 以最終分配到的為準(zhǔn)虎韵，看能cover住多少個桶，向下取整
            nbuckets = up / t.bucket.size
        }
    }

    // 這里分兩種情況，第一種是dirtyalloc參數(shù)是nil
    // 這種情況就new一個bucket數(shù)組即可
    // 第二種就是dirtyalloc參數(shù)不是nil绳泉，那就復(fù)用這塊內(nèi)存而不新申請
    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
        // 使用前需要清空內(nèi)存塊數(shù)據(jù)
        // 區(qū)分兩種四苇，一種是包含指針的榆骚，一種是不包含的
        // 這里區(qū)分主要是寫屏障相關(guān)的，不詳細(xì)說了
        if t.bucket.ptrdata != 0 {
            memclrHasPointers(buckets, size)
        } else {
            memclrNoHeapPointers(buckets, size)
        }
    }

    // 如果申請了備用空間
    if base != nbuckets {
        // We preallocated some overflow buckets.
        // To keep the overhead of tracking these overflow buckets to a minimum,
        // we use the convention that if a preallocated overflow bucket's overflow
        // pointer is nil, then there are more available by bumping the pointer.
        // We need a safe non-nil pointer for the last overflow bucket; just use buckets.
        // base是要申請的桶數(shù)纲缓，刨掉這部分占用的內(nèi)存喊废，后面就是多申請的，nextOverflow指向后面的多余部分
        // last是找到內(nèi)存塊最后一個桶的位置工闺，然后讓最后一個桶的overflow指向頭桶(準(zhǔn)確的說是指向指向頭桶的指針)，具體實現(xiàn)后面會說
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    // 返回頭桶和預(yù)留桶地址
    return buckets, nextOverflow
}

// bucketShift returns 1<<b, optimized for code generation.
// 計算2^b
func bucketShift(b uint8) uintptr {
    // Masking the shift amount allows overflow checks to be elided.
    // 等價于1 << b
    // 這里b & (sys.PtrSize*8 - 1) 等價于 b & (64 - 1) (假設(shè)是64位機(jī)器)
    // 而b & (64 - 1) <= 63颓屑，避免移位溢出，因為64位機(jī)器纫塌，最多只能左移63次
    return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}

// 找到bucket的overflow，bucket的結(jié)構(gòu)是bmap避除，上面說過bmap編譯時候會通過reflect加點料怎披，其中就有overflow
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
    // 這里強制轉(zhuǎn)成**bmap是沒有問題的握联，都是指針類型斤讥，所以類型是指向(指向bmap的指針)的指針
    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}

訪問

map的訪問有5個方法

• mapaccess1 返回指向h[k]的指針
• mapaccess2 返回指向h[k]的指針和一個bool類型變量，用于標(biāo)記map中是否有對應(yīng)的key，還記得 v, ok := h[k]的寫法嗎
• mapaccessK 同時返回kv钞速，用于map遍歷
• mapaccess1_fat和mapaccess2_fat 這兩都是mapaccess1的包裝，如果map中不存在k商玫，對應(yīng)返回其類型零值狂打，mapaccess2_fat多返回一個bool類型變量，功能同mapaccess2
  看下mapaccess1的源碼(其他的基本差別不大诬辈，不另贅述)

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
// mapaccess1返回指向h[key]的指針酵使，永遠(yuǎn)不會返回nil
// 如果key不存在，會返回一個指向特殊對象的指針焙糟，方便其他方法進(jìn)行判斷
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    // 如果h沒有初始化或者沒有存任何kv對就直接返回特殊指針
    if h == nil || h.count == 0 {
        // 這里會檢測key是否可以被hash
        // 具體原因看 https://github.com/golang/go/issues/23734
        // 大致意思就是如果傳進(jìn)來的k是slice口渔、map或者func這些無法比較的key，應(yīng)該給出具體的錯誤
        // 如果這里沒有這個檢查酬荞，返回對應(yīng)的類型零值搓劫，就會產(chǎn)生規(guī)則混淆
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        // 返回特殊指針
        return unsafe.Pointer(&zeroVal[0])
    }
    // 如果有寫map操作，拋異常混巧，所以map不是并發(fā)安全的
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 計算hash值
    hash := t.hasher(key, uintptr(h.hash0))
    // 這里m = (1 << b) -1枪向，假設(shè)b=4 那么m=000...001111（即低四位都是1，其余都是0咧党，這里用二進(jìn)制表示）
    m := bucketMask(h.B)
    // 通過hash的二進(jìn)制低b位計算目標(biāo)桶號
    // 假設(shè)b=4秘蛔，hash的低4位是0011，那么(hash&m) = xxx...xxx0011 & 000...001111 = 000...000011 = 3傍衡，即3號桶就是目標(biāo)桶
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 這段邏輯是為了兼容map擴(kuò)容深员，擴(kuò)容后面會說到
    // 如果h.oldbuckets不等于nil，說明正在擴(kuò)容
    if c := h.oldbuckets; c != nil {
        // 如果不是等量擴(kuò)容蛙埂，新桶的h.B會加1即桶的數(shù)量翻倍
        // 那么舊桶對應(yīng)的m就是新桶的一半倦畅，需要右移一位
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        // 找到舊桶中的目標(biāo)桶
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        // 如果目標(biāo)桶還沒遷移到新桶，就將舊桶的目標(biāo)桶作為最終目標(biāo)桶
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // 通過hash二進(jìn)制高八位得到top绣的，tophash后面會說
    top := tophash(hash)
bucketloop:
    // 遍歷目標(biāo)桶以及對應(yīng)的所有溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 遍歷每個桶的8個kv對
        for i := uintptr(0); i < bucketCnt; i++ {
            // 先看b.tophash數(shù)組中是否有top叠赐，做一次快速篩選
            if b.tophash[i] != top {
                // 這里有一個特殊標(biāo)識emptyRest，代表后面包括所有的桶都是空的屡江，可以直接跳出兩層循環(huán)結(jié)束查找
                // 關(guān)于如何維護(hù)emptyRest芭概，后面會說到
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 跳過內(nèi)層循環(huán)，快速篩選成功
                continue
            }
            // 找到對應(yīng)的k
            // 這里dataOffset其實就是bmap后的第一個字節(jié)的位置惩嘉，具體怎么來的后面會說
            // 還記得上面說的吧罢洲，bmap在編譯期間會加料，就是在bmap后面新增k,v,pad和overflow
            // 這里dataOffset就是第一個k的位置對應(yīng)bmap首字節(jié)的字節(jié)位移
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // 如果k存的是指針文黎，就進(jìn)行解引用
            if t.indirectkey() {
                // 這里面用到了*unsafe.Pointer惹苗，請注意*unsafe.Pointer是安全的殿较，所以可以強制轉(zhuǎn)換，就類似(*int)
                // 具體可以看這里 https://go101.org/article/unsafe.html
                // 反正記住兩個go編譯器的規(guī)則
                // 1. 一個安全的指針可以轉(zhuǎn)換為不安全的指針即unsafe.Pointer鸽粉，反之亦然
                // 2. 一個uintptr類型的值可以轉(zhuǎn)換為不安全的指針斜脂，反之亦然，但是要注意如果指針是nil触机，則不應(yīng)該轉(zhuǎn)換為uintptr帚戳，并進(jìn)行算術(shù)運算
                // 對于未知類型的k，我們可以通過如下方式來解引用得到具體的值
                k = *((*unsafe.Pointer)(k))
            }
            // 如果k相等說明找到了
            // 這里就是為什么map的key必須是可以比較的
            if t.key.equal(key, k) {
                // 先跳過bmap的tophash儡首，再跳過8個k片任，再跳過i個v，就是要找的v
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                // 如果v存的是指針蔬胯，解引用对供，同上
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                // 返回v
                return e
            }
        }
    }
    // 返回不存在標(biāo)識
    return unsafe.Pointer(&zeroVal[0])
}

// tophash calculates the tophash value for hash.
// 計算tophash
func tophash(hash uintptr) uint8 {
    // 取到hash的高8位
    top := uint8(hash >> (sys.PtrSize*8 - 8))
    // minTopHash=5, 如果top < 5，則top += 5
    // 這是因為0,1,2,3,4都是特殊標(biāo)記值氛濒，有另外的作用产场，makemap解讀的時候說過，tophash不僅有快篩的作用舞竿，還會有標(biāo)記的作用
    // 所以當(dāng)計算出來的tophash與標(biāo)記值沖突時京景，進(jìn)行沖突解決
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

// data offset should be the size of the bmap struct, but needs to be
// aligned correctly. For amd64p32 this means 64-bit alignment
// even though pointers are 32 bit.
// 這里通過unsafe.Offsetof來計算bmap的size，是為了適配不同的處理器架構(gòu)
dataOffset = unsafe.Offsetof(struct {
    b bmap
    v int64
}{}.v)

寫入

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
// 寫map
// 里面可能會觸發(fā)初始化操作骗奖，擴(kuò)容操作
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // h是nil确徙，直接panic
    // 比如 var m map[int]int，此時m=nil执桌，操作m[1]=1就會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)
    }
    // 寫并發(fā)異常
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 計算hash
    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write.
    // 這里在寫入計算完hash之后寫入寫標(biāo)記鄙皇，因為計算hash可能會panic，而這個時候map并沒有發(fā)生實際的寫操作
    h.flags ^= hashWriting

    // 還記得makemap吧仰挣，有可能會延遲分配桶伴逸，這里就是延遲分配的地方
    if h.buckets == nil {
        // new一個桶
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    // 尋找目標(biāo)桶
    bucket := hash & bucketMask(h.B)
    // 如果正在擴(kuò)容，那么現(xiàn)在的目標(biāo)桶bucket是在新桶上
    if h.growing() {
        // 保證目標(biāo)桶對應(yīng)的舊桶已經(jīng)遷移
        // growWrok是實際操作桶遷移的函數(shù)
        // 整個map的擴(kuò)容過程中膘壶，舊桶遷移到新桶都是由寫操作(寫入/刪除)觸發(fā)逐步遷移的
        // 這么做也是為了不影響map的正常讀寫速度违柏，類似redis擴(kuò)容，一個套路
        // 具體如何擴(kuò)容后面會說
        growWork(t, h, bucket)
    }
    // 遷移完后就可以直接寫目標(biāo)桶了
    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 {
        // 遍歷目標(biāo)桶的8對kv
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果tophash[i]不相等香椎，說明要么就是存的別的kv對，要么就是空的
            if b.tophash[i] != top {
                // 如果是空的且預(yù)備寫入位置還沒找到
                // 就將當(dāng)前空的位置作為預(yù)備寫入tophash的位置
                // 這里還需要繼續(xù)往后找禽篱，因為后面可能會找到目標(biāo)kv
                // 刪除操作會導(dǎo)致tophash中間有空檔
                if isEmpty(b.tophash[i]) && inserti == nil {
                    // 預(yù)備寫入tophash的位置
                    inserti = &b.tophash[i]
                    // 預(yù)備寫入k的位置
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    // 預(yù)備寫入v的位置
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                // tophash[i]為空有兩種
                // 一種是當(dāng)前tophash[i]為空畜伐，還有一種是當(dāng)前及后面所有(包括溢出桶)都為空
                // 回想下mapaccess1中說的emptyRest標(biāo)識
                // 如果后面都是空，就不用繼續(xù)找了躺率，跳出兩層循環(huán)
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 否則就繼續(xù)找
                continue
            }
            // 如果通過tophash快速找到了玛界，就繼續(xù)找到對應(yīng)的k
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // 這里不再細(xì)說了万矾，上面說過了
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // k不相等，繼續(xù)找
            if !t.key.equal(key, k) {
                continue
            }
            // already have a mapping for key. Update it.
            // k相等慎框，找到目標(biāo)kv
            // 這里需要判斷是否把k覆蓋一遍
            // 有點迷惑良狈，就是k都相等了，為啥要覆蓋呢
            // 看看這里cmd/compile/internal/reflectdata/reflect.go
            // 具體我也不是很清楚笨枯，大概意思就是map[0]和map[+0]和map[-0]是一個kv薪丁，但是k不一樣
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            // 找到對應(yīng)v的位置
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            // 跳到最后
            goto done
        }
        
        // 后面還有桶就繼續(xù)找下一個桶
        // 沒有桶了就跳出循環(huán)，說明需要寫入新的kv
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    // Did not find mapping for key. Allocate new cell & add entry.

    // If we hit the max load factor or we have too many overflow buckets,
    // and we're not already in the middle of growing, start growing.
    // 到這里說明沒找到目標(biāo)kv馅精，也就是說是新插入一對kv严嗜，h.count需要加1，就觸發(fā)判斷是否擴(kuò)容了
    // 如果map過載或者溢出桶太多洲敢，就會觸發(fā)擴(kuò)容漫玄，具體判斷過載和溢出的函數(shù)后面會說
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        // 擴(kuò)容初始化，會判斷是否需要分配新桶
        hashGrow(t, h)
        // 擴(kuò)容準(zhǔn)備好后压彭，就從頭再來一遍
        // 一個是為了觸發(fā)當(dāng)前桶遷移睦优，二是遷移后會在新桶繼續(xù)執(zhí)行寫操作
        goto again // Growing the table invalidates everything, so try again
    }

    // 如果inserti也是nil，說明目標(biāo)桶及其所有的溢出桶都滿了
    // 需要新建一個溢出桶
    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        // 新建一個溢出桶壮不，newoverflow函數(shù)后面會說
        newb := h.newoverflow(t, b)
        // 指定tophash的位置
        inserti = &newb.tophash[0]
        // 指定k的位置
        insertk = add(unsafe.Pointer(newb), dataOffset)
        // 指定v的位置
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/elem at insert position
    // 是否存指針汗盘，indirectkey上面說過，不再細(xì)說
    if t.indirectkey() {
        // 先new一個k
        kmem := newobject(t.key)
        // 再賦值到桶中k所在位置的內(nèi)存中
        *(*unsafe.Pointer)(insertk) = kmem
        // 這里邏輯上同等于insertk = *insertk忆畅，讓insertk指向新申請的k的內(nèi)存塊
        insertk = kmem
    }
    // 同上
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    // 新插入的kv的k賦值到insertk指向的內(nèi)存
    typedmemmove(t.key, insertk, key)
    // 新桶的tophash[i] = top
    *inserti = top
    // kv對數(shù)加1
    h.count++

done:
    // 最后檢查是否有并發(fā)異常
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    // &^是置零操作衡未，同等于h.flags &= ^hashWriting
    // 清除寫標(biāo)識
    h.flags &^= hashWriting
    if t.indirectelem() {
        // 這里跟上面insertk = kmem的意思是一樣的，就是拿到v的實際值家凯，即一個指向某個內(nèi)存塊的指針
        elem = *((*unsafe.Pointer)(elem))
    }
    // 返回v
    // 這里就結(jié)束了缓醋，有人會問，上面對k進(jìn)行了賦值绊诲，但是沒有對v賦值送粱，只是返回而已
    // 其實這里調(diào)用方拿到v之后，會在外面進(jìn)行賦值掂之，具體可以通過go tool compile編譯一段寫map的代碼看看
    return elem
}

// growing reports whether h is growing. The growth may be to the same size or bigger.
// map擴(kuò)容的時候會創(chuàng)建新桶抗俄，舊桶會變成oldbuckets
// 這里通過判斷是否有oldbuckets來確認(rèn)map是否在擴(kuò)容
func (h *hmap) growing() bool {
    return h.oldbuckets != nil
}

// 擴(kuò)容的遷移操作
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // make sure we evacuate the oldbucket corresponding
    // to the bucket we're about to use
    // 先遷移指定桶
    // evacuate函數(shù)，在擴(kuò)容部分會單獨詳細(xì)說
    evacuate(t, h, bucket&h.oldbucketmask())

    // evacuate one more oldbucket to make progress on growing
    // 如果還沒遷移完
    // 每次還會嘗試多遷移一個桶
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

// 新建一個溢出桶
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
    var ovf *bmap
    // 還記得nextOverflow吧世舰，makemap的時候可能會申請預(yù)備桶空間动雹，就是用nextOverflow來標(biāo)記內(nèi)存位置的
    // 這里派上用場了
    if h.extra != nil && h.extra.nextOverflow != nil {
        // We have preallocated overflow buckets available.
        // See makeBucketArray for more details.
        ovf = h.extra.nextOverflow
        // 再回憶一下makemap，當(dāng)時申請預(yù)備桶空間后跟压，還將最后一個桶的overflow指向頭桶
        // 這里也派上用場了胰蝠，通過這個能判斷是否是預(yù)備桶的最后一個桶
        if ovf.overflow(t) == nil {
            // We're not at the end of the preallocated overflow buckets. Bump the pointer.
            // 如果不是最后一個桶，那就讓nextOverflow往后挪一個桶，即釋放一個預(yù)備桶到正式桶
            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
        } else {
            // This is the last preallocated overflow bucket.
            // Reset the overflow pointer on this bucket,
            // which was set to a non-nil sentinel value.
            // 如果是最后一個桶茸塞，說明預(yù)備桶用完了躲庄，那么nextOverflow指向nil，最后一個桶的overflow指向nil
            ovf.setoverflow(t, nil)
            h.extra.nextOverflow = nil
        }
    } else {
        // 如果沒有申請預(yù)備桶空間或者預(yù)備桶之前就用完了钾虐，就申請一個新的桶
        ovf = (*bmap)(newobject(t.bucket))
    }
    // 更新溢出桶的計數(shù)
    h.incrnoverflow()
    // 這個ptrdata用于判斷bucket是否包含指針
    // ptrdata=0表示不包含噪窘，具體可以看 cmd/compile/internal/types/size.go PtrDataSize函數(shù)
    if t.bucket.ptrdata == 0 {
        // 如果bucket是不包含指針的，那么如makemap所說的效扫，就需要有h.extra.overflow來兜住所有指向溢出桶的指針
        // 檢查并創(chuàng)建一個overflow倔监，createOverflow方法很簡單，不細(xì)說了
        h.createOverflow()
        // 將指向新桶的指針保存到overflow中
        *h.extra.overflow = append(*h.extra.overflow, ovf)
    }
    // 將當(dāng)前桶連接上新的溢出桶
    b.setoverflow(t, ovf)
    return ovf
}


// incrnoverflow increments h.noverflow.
// noverflow counts the number of overflow buckets.
// This is used to trigger same-size map growth.
// See also tooManyOverflowBuckets.
// To keep hmap small, noverflow is a uint16.
// When there are few buckets, noverflow is an exact count.
// When there are many buckets, noverflow is an approximate count.
// 這里會新增noverflow
func (h *hmap) incrnoverflow() {
    // We trigger same-size map growth if there are
    // as many overflow buckets as buckets.
    // We need to be able to count to 1<<h.B.
    // 如果bucket < 2^16荡短，就老老實實加1
    if h.B < 16 {
        h.noverflow++
        return
    }
    // Increment with probability 1/(1<<(h.B-15)).
    // When we reach 1<<15 - 1, we will have approximately
    // as many overflow buckets as buckets.
    // 否則就概率性的加1丐枉，也就是說如果B很大，buckets很多掘托，那么這個值就是個近似值
    // 就是當(dāng)B很大的時候瘦锹，可以適當(dāng)降低因為溢出桶太多而擴(kuò)容的概率
    mask := uint32(1)<<(h.B-15) - 1
    // Example: if h.B == 18, then mask == 7,
    // and fastrand & 7 == 0 with probability 1/8.
    if fastrand()&mask == 0 {
        h.noverflow++
    }
}

擴(kuò)容

// evacDst is an evacuation destination.
// evacDst用于桶遷移
type evacDst struct {
    // 遷移的目標(biāo)桶
    b *bmap          // current destination bucket
    // 當(dāng)前桶的遷移進(jìn)度，即遷移了i對kv
    i int            // key/elem index into b
    // kv的遷移目標(biāo)位置
    k unsafe.Pointer // pointer to current key storage
    e unsafe.Pointer // pointer to current elem storage
}

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
// 判斷溢出桶是否過多
// 如果常規(guī)桶 > 2^15闪盔，那么就判斷溢出桶數(shù)是否 >= 2^15
// 否則就判斷溢出桶是否 >= 常規(guī)桶
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    // If the threshold is too low, we do extraneous work.
    // If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
    // "too many" means (approximately) as many overflow buckets as regular buckets.
    // See incrnoverflow for more details.
    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)
}

// 桶擴(kuò)容
// 如果是負(fù)載弯院，那就讓常規(guī)桶的數(shù)量翻倍
// 如果是溢出桶太多，常規(guī)桶的數(shù)量不變泪掀，整理所有桶使得kv排列更緊湊
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.
    // 是否擴(kuò)充常規(guī)桶標(biāo)識
    bigger := uint8(1)
    // 每增加一個kv對听绳，都需要判斷是否需要擴(kuò)容然后調(diào)用該方法進(jìn)行擴(kuò)容
    // 所以是h.count+1
    if !overLoadFactor(h.count+1, h.B) {
        // 如果不是負(fù)載太高，bigger置為0
        bigger = 0
        // 標(biāo)記為等容量擴(kuò)容
        h.flags |= sameSizeGrow
    }
    // 原來的桶標(biāo)記為舊桶
    oldbuckets := h.buckets
    // 申請新桶
    // 新桶的常規(guī)桶數(shù)量是2^(h.B+bigger)异赫，如果bigger=1椅挣，就是翻倍，否則常規(guī)桶數(shù)不變
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    // 這里是將舊桶的迭代標(biāo)識復(fù)制給新桶塔拳，具體使用在桶的遍歷中會說到
    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // commit the grow (atomic wrt gc)
    // 更新h.B
    h.B += bigger
    // 更新標(biāo)識
    h.flags = flags
    // 更新舊桶
    h.oldbuckets = oldbuckets
    // 更新新桶
    h.buckets = newbuckets
    // 標(biāo)記桶遷移進(jìn)度
    h.nevacuate = 0
    // 新桶的溢出桶數(shù)量置為0
    h.noverflow = 0

    // 將指向舊溢出桶的指針挪到oldoverflow中
    // 因為overflow需要給新的溢出桶使用
    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")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    // 新申請的桶可能申請了預(yù)備桶空間鼠证，nextOverflow指向?qū)?yīng)內(nèi)存塊
    // 不記得了可以回去看下makeBucketArray函數(shù)
    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().
}

// 擴(kuò)容桶遷移
// 參數(shù)里面會有個舊桶編號oldbucket
// 舊桶在寫時觸發(fā)遷移操作
// 該函數(shù)在hashGrow擴(kuò)容之后調(diào)用
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 根據(jù)桶號找到舊桶
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    // 計算舊桶的常規(guī)桶數(shù)(不包括溢出桶)
    // 其實就是1 << h.B，這里的h.B是舊桶的
    newbit := h.noldbuckets()
    // 如果舊桶沒有遷移到新桶
    if !evacuated(b) {
        // TODO: reuse overflow buckets instead of using new ones, if there
        // is no iterator using the old buckets.  (If !oldIterator.)

        // xy contains the x and y (low and high) evacuation destinations.
        // 定義兩個evacDst靠抑，evacDst其實用來對應(yīng)新桶的前半部分和后半部分
        // 還記得吧量九，過載擴(kuò)容，新桶的h.B = 舊桶的h.B + 1
        // 假設(shè)原來的h.B=3颂碧，只需要取hash的后三位來計算桶編號即可
        // 擴(kuò)容后h.B=4荠列，就需要取hash的后四位來計算桶編號
        // hash的后第四位可能是1/0，如果是0桶編號不變载城，落到新桶的前半部分肌似，如果是1則落到桶的后半部分
        var xy [2]evacDst
        x := &xy[0]
        // xy[0]對應(yīng)前半部分
        // 確定對應(yīng)前半部分的哪個桶
        // 因為前半部分的桶編號不變，所以這里編號就是參數(shù)oldbucket
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        // 對應(yīng)桶的kv起始位置
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.e = add(x.k, bucketCnt*uintptr(t.keysize))

        // 如果是過載擴(kuò)容
        if !h.sameSizeGrow() {
            // Only calculate y pointers if we're growing bigger.
            // Otherwise GC can see bad pointers.
            // xy[1]對應(yīng)后半部分
            y := &xy[1]
            // 因為是后半部分诉瓦，所以hash的后第h.B+1位是1(這里的h.B對應(yīng)舊桶)
            // 所以這里加上newbit
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
            // 對應(yīng)桶的kv起始位置
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            y.e = add(y.k, bucketCnt*uintptr(t.keysize))
        }

        // 遍歷舊桶以及對應(yīng)的溢出桶
        for ; b != nil; b = b.overflow(t) {
            // 找到kv起始位置
            k := add(unsafe.Pointer(b), dataOffset)
            e := add(k, bucketCnt*uintptr(t.keysize))
            // 遍歷8對kv
            for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
                top := b.tophash[i]
                // 如果tophash[i]是空锈嫩，繼續(xù)找下一個kv對
                if isEmpty(top) {
                    b.tophash[i] = evacuatedEmpty
                    continue
                }
                // 檢查tophash[i]是否是合法值受楼，防止重入
                if top < minTopHash {
                    throw("bad map state")
                }
                // 取到k的值
                k2 := k
                if t.indirectkey() {
                    k2 = *((*unsafe.Pointer)(k2))
                }
                // useY用于標(biāo)識是否使用新桶的后半部分，這取決于k的hash值
                var useY uint8
                // 如果是過載擴(kuò)容
                if !h.sameSizeGrow() {
                    // Compute hash to make our evacuation decision (whether we need
                    // to send this key/elem to bucket x or bucket y).
                    // 計算k的hash值
                    hash := t.hasher(k2, uintptr(h.hash0))
                    // 檢查特殊情況呼寸，具體在背景部分貼的其他文章里面有詳細(xì)描述，這里不再贅述
                    // 大致意思就是對于某些特殊的k猴贰，每次計算出來的hash值都不一樣对雪，所以沒法通過hash值來判斷是放到新桶的前半部分還是后半部分
                    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.
                        // 約定一種規(guī)則來處理這種特殊的k，隨機(jī)放到新桶前/后半部分
                        useY = top & 1
                        // 因為hash變了米绕，所以top也變了
                        top = tophash(hash)
                    } else {
                        // 通過hash來判斷
                        if hash&newbit != 0 {
                            // 如果判斷是落到后半部分瑟捣，useY = 1
                            useY = 1
                        }
                    }
                }
                // 這里是檢查落到新桶前半部分的標(biāo)記值和落到后半部分的標(biāo)記值是否符合后續(xù)的計算邏輯
                // 因為這兩個標(biāo)記有可能會變，即使變了栅干，也需要符合下面的規(guī)則
                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                    throw("bad evacuatedN")
                }
                // 通過useY的不同值來加和出不同的標(biāo)記即evacuatedX和evacuatedY
                // 這就是上面if判斷的原因
                // 同時賦值給tophash[i]來保存標(biāo)記迈套，還記得吧，這就是之前說過的tophash[i]的第二種功能
                b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
                // 確認(rèn)使用哪個evacDst
                dst := &xy[useY]                 // evacuation destination

                // 這里檢測dst對應(yīng)的桶即dst.b是否已經(jīng)滿了
                // 上面的for循環(huán)是遍歷舊桶碱鳞，而且只有kv對不為空的時候桑李，才會挪動到新桶，dst.i才會+1
                // 通過上述操作窿给，新桶就會跳過舊桶的空kv對贵白，達(dá)到緊湊的效果
                if dst.i == bucketCnt {
                    // 既然當(dāng)前桶滿了，那就新建一個溢出桶
                    dst.b = h.newoverflow(t, dst.b)
                    // dst.i置為0崩泡，重新為新建的溢出桶計數(shù)
                    dst.i = 0
                    // 重置k和e禁荒，指向溢出桶kv的起始位置
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
                }
                // 設(shè)置新目標(biāo)桶的tophash
                // 這里通過位與操作來避免溢出
                dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
                // 遷移k的值到新目標(biāo)桶
                // 區(qū)分指針和非指針
                if t.indirectkey() {
                    *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
                } else {
                    typedmemmove(t.key, dst.k, k) // copy elem
                }
                // 遷移v的值到新目標(biāo)桶
                if t.indirectelem() {
                    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
                } else {
                    typedmemmove(t.elem, dst.e, e)
                }
                // 計數(shù)加1
                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.
                // k和e分別向后挪，指向下一個kv對
                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.
        // 如果舊桶沒有在遍歷并且bucket有指針
        // 就將舊目標(biāo)桶(除了tophash)以及對應(yīng)溢出桶占用的內(nèi)存都釋放掉角撞，輔助gc呛伴，減少內(nèi)存占用
        // 保留目標(biāo)桶的tophash是為了標(biāo)記該桶以及對應(yīng)的溢出桶都已經(jīng)被遷移了
        // 判斷bucket是否包含指針是因為如果bucket不包含指針，那么指向所有溢出桶的指針會保留在oldoverflow中
        // 而oldoverflow保留的是全部溢出桶谒所，也沒法部分刪掉热康，所以即使清空了溢出桶的內(nèi)存，依然有指針指向百炬，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.
            ptr := add(b, dataOffset)
            n := uintptr(t.bucketsize) - dataOffset
            memclrHasPointers(ptr, n)
        }
    }
    // 如果當(dāng)前桶編號和遷移進(jìn)度一致褐隆，就觸發(fā)遷移進(jìn)度的更新
    if oldbucket == h.nevacuate {
        advanceEvacuationMark(h, t, newbit)
    }
}

// 更新桶的遷移進(jìn)度也是一個隨機(jī)+漸進(jìn)的過程
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
    // 進(jìn)度加1
    h.nevacuate++
    // Experiments suggest that 1024 is overkill by at least an order of magnitude.
    // Put it in there as a safeguard anyway, to ensure O(1) behavior.
    // 這個主要是為了控制for循環(huán)的次數(shù)，以保證map的O(1)操作
    stop := h.nevacuate + 1024
    if stop > newbit {
        stop = newbit
    }
    // 循環(huán)統(tǒng)計遷移的桶數(shù)并更新遷移進(jìn)度
    for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
        h.nevacuate++
    }
    // 最終所有的桶都遷移完畢剖踊，開始清理舊桶
    if h.nevacuate == newbit { // newbit == # of oldbuckets
        // Growing is all done. Free old main bucket array.
        // 釋放舊桶
        h.oldbuckets = nil
        // Can discard old overflow buckets as well.
        // If they are still referenced by an iterator,
        // then the iterator holds a pointers to the slice.
        if h.extra != nil {
            // 清理指向舊溢出桶的指針
            h.extra.oldoverflow = nil
        }
        // 清空等量擴(kuò)容標(biāo)識
        h.flags &^= sameSizeGrow
    }
}

刪除

// 刪除map中的指定kv
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)
  }
  // 前面說過庶弃，不細(xì)說了
  if h == nil || h.count == 0 {
    if t.hashMightPanic() {
      t.hasher(key, 0) // see issue 23734
    }
    return
  }
  // 同上
  if h.flags&hashWriting != 0 {
    throw("concurrent map writes")
  }

  // 計算k的hash值
  hash := t.hasher(key, uintptr(h.hash0))

  // Set hashWriting after calling t.hasher, since t.hasher may panic,
  // in which case we have not actually done a write (delete).
  // 設(shè)置寫標(biāo)記
  h.flags ^= hashWriting

  // 跟mapassign同樣的操作
  // 獲取桶，判斷是否擴(kuò)容德澈，桶遷移等一系列操作
  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:
  // 遍歷目標(biāo)桶及溢出桶找需要刪除的kv
  for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        // emptyRest標(biāo)記前面說過
        if b.tophash[i] == emptyRest {
          break search
        }
        continue
      }
      // tophash篩選找到歇攻，再判斷k是否相等
      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
      }
      // Only clear key if there are pointers in it.
      // 如果k保存的是指針，直接指向nil
      // 如果k包含指針梆造，比如是個struct缴守，包著指針葬毫，就調(diào)用對應(yīng)方法清理內(nèi)存
      if t.indirectkey() {
        *(*unsafe.Pointer)(k) = nil
      } else if t.key.ptrdata != 0 {
        memclrHasPointers(k, t.key.size)
      }
      // 找到k對應(yīng)的v
      // 同樣的操作，清空v
      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[i]
      // 標(biāo)識空屡穗，用于快速篩選
      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.
      // 后面這些操作主要是為了維護(hù)emptyRest標(biāo)志贴捡，該標(biāo)志代表的意思前面說過了
      // 怎么維護(hù)呢，先以被刪除的kv對的位置i向后看一位
      // 兩種情況村砂，第一種被刪除的kv是該桶的最后一個kv對烂斋，那么如果有溢出桶就繼續(xù)看溢出桶的tophash[0]標(biāo)識，否則就向前追溯
      // 第二種被刪除的kv不是該桶的最后一個kv對础废，那就看后一個tophash標(biāo)識即tophash[i+1]
      // 如果tophash[i+1]是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
        }
      }
      // 這就是追溯過程
      // 通過上面分析可知如果tophash[i+1]或者溢出桶的tophash[0]等于emptyRest
      // 那么當(dāng)前的tophash[i]也可設(shè)置為emptyRest
      // 既然當(dāng)前的tophash[i]是emptyRest，那么前面的所有連續(xù)的n個等于emptyOne的空的tophash也都可以設(shè)置成emptyRest
      // 有點類似抽屜原理评腺，不了解的可以看看raft協(xié)議
      for {
        // 當(dāng)前tophash設(shè)置為emptyRest
        b.tophash[i] = emptyRest
        // 如果是頭部kv
        if i == 0 {
          // 如果是頭桶帘瞭，說明追溯完了
          if b == bOrig {
            break // beginning of initial bucket, we're done.
          }
          // Find previous bucket, continue at its last entry.
          // 否則就找當(dāng)前桶的前面那個桶
          // 因為桶之間只有單向順序指針連接，所以這里需要通過遍歷來找
          c := b
          for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
          }
          // 找到上個桶后蒿讥，從最后一個kv對逐步逆序檢查tophash標(biāo)識
          i = bucketCnt - 1
        } else {
          // 如果不是頭部kv蝶念，繼續(xù)追溯
          i--
        }
        // 一旦找到某個tophash[i]不是空，則跳出循環(huán)诈悍，追溯完畢
        if b.tophash[i] != emptyOne {
          break
        }
      }
    notLast:
      // map的元素個數(shù)減一
      h.count--
      // Reset the hash seed to make it more difficult for attackers to
      // repeatedly trigger hash collisions. See issue 25237.
      // 如果map被清空了祸轮，就重置hash種子
      // 這么做可以提升hash沖突的攻擊難度
      // 具體原因見 https://github.com/golang/go/issues/25237
      if h.count == 0 {
        h.hash0 = fastrand()
      }
      // 跳出外層循環(huán)
      break search
    }
  }

  // 這里跟mapassign一樣的，不細(xì)說了
  if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
  }
  h.flags &^= hashWriting
}

清空

// mapclear deletes all keys from a map.
// 清空整個map
func mapclear(t *maptype, h *hmap) {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapclear)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
    }

    // 本來就是空的
    if h == nil || h.count == 0 {
        return
    }

    // 并發(fā)寫控制
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 設(shè)置寫標(biāo)志
    h.flags ^= hashWriting

    // 清空等量擴(kuò)容標(biāo)志
    h.flags &^= sameSizeGrow
    // 清空舊桶侥钳，數(shù)據(jù)都清空了适袜，就沒必要擴(kuò)容了，舊桶也就不需要了
    h.oldbuckets = nil
    // 清空各種計數(shù)器舷夺，遷移進(jìn)度計數(shù)器苦酱，溢出桶計數(shù)器和kv對數(shù)量計數(shù)器
    h.nevacuate = 0
    h.noverflow = 0
    h.count = 0

    // Reset the hash seed to make it more difficult for attackers to
    // repeatedly trigger hash collisions. See issue 25237.
    // 重置hash種子，原因之前說過了
    h.hash0 = fastrand()

    // Keep the mapextra allocation but clear any extra information.
    // 清空擴(kuò)展信息给猾，釋放內(nèi)存
    // 包括指向新舊溢出桶的所有指針和指向預(yù)備桶內(nèi)存塊指針
    if h.extra != nil {
        *h.extra = mapextra{}
    }

    // makeBucketArray clears the memory pointed to by h.buckets
    // and recovers any overflow buckets by generating them
    // as if h.buckets was newly alloced.
    // 通過makeBucketArray來清空并復(fù)用map的buckets
    // 這里的buckets就是之前通過該方法申請的
    _, nextOverflow := makeBucketArray(t, h.B, h.buckets)
    // 還記得makeBucketArray會多申請一部分空間作為預(yù)備桶吧
    // 這里只進(jìn)行清空操作疫萤，之前哪些是常規(guī)桶空間哪些是預(yù)備桶空間不變，方便再次寫入kv時減少溢出桶的申請次數(shù)
    if nextOverflow != nil {
        // If overflow buckets are created then h.extra
        // will have been allocated during initial bucket creation.
        h.extra.nextOverflow = nextOverflow
    }

    // 并發(fā)寫控制
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    // 清空寫標(biāo)記
    h.flags &^= hashWriting
}

這里有人可能比較困惑敢伸，因為map并未提供清空操作扯饶，mapclear何時會調(diào)用呢，這里先看一段代碼

func main() {
    m := make(map[int]int, 2)
    for i := 0; i < 5; i++ {
        m[i] = i
    }
    for k := range m {
        delete(m, k)
    }
}

通過go tool compile -S編譯出來的匯編代碼中有一行如下

image.png

遍歷

// A hash iteration structure.
// If you modify hiter, also change cmd/compile/internal/reflectdata/reflect.go to indicate
// the layout of this structure.
// 用于map迭代的數(shù)據(jù)結(jié)構(gòu)
type hiter struct {
    // 當(dāng)前迭代的k琢歇，如果key=nil兰怠，說明迭代結(jié)束了
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
    // 當(dāng)前迭代的v
    elem        unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    // 指向當(dāng)前正在遍歷的桶
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    // 標(biāo)記從哪個桶開始遍歷梦鉴，每次是隨機(jī)的
    startBucket uintptr        // bucket iteration started at
    // 標(biāo)記總遍歷桶的那個kv對開始遍歷，每次也是隨機(jī)的
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    // 標(biāo)記是否從最后一個桶回繞到了第一個桶
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}


// mapiterinit initializes the hiter struct used for ranging over maps.
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
// Both need to have zeroed hiter since the struct contains pointers.
// 初始化hiter
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
    }

    if h == nil || h.count == 0 {
        return
    }

    if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
        throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
    }
    it.t = t
    it.h = h

    // grab snapshot of bucket state
    // 保留快照
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        // Allocate the current slice and remember pointers to both current and old.
        // This preserves all relevant overflow buckets alive even if
        // the table grows and/or overflow buckets are added to the table
        // while we are iterating.
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }

    // decide where to start
    // 找隨機(jī)開始位置
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))

    // iterator state
    // bucket用于記錄當(dāng)前遍歷的桶序號揭保，剛開始等于startBucket
    // 注意it.bucket始終都是新桶的編號肥橙，即使桶擴(kuò)容了
    // 遍歷的順序就是從新桶的第bucket個桶開始(即startBucket)，縱向向下遍歷所有溢出桶掖举，遍歷完后橫向向右繼續(xù)遍歷其他常規(guī)桶快骗，遍歷到尾部后繼續(xù)回繞到頭桶，重復(fù)縱向橫向遍歷直到回到startBucket號桶
    // 遍歷每一個bucket號桶的時候還需要檢查是否是在擴(kuò)容塔次，如果在擴(kuò)容，還需要找到對應(yīng)未遷移的舊桶名秀，對舊桶進(jìn)行縱向遍歷
    it.bucket = it.startBucket

    // Remember we have an iterator.
    // Can run concurrently with another mapiterinit().
    // 設(shè)置迭代標(biāo)識
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
        atomic.Or8(&h.flags, iterator|oldIterator)
    }

    // 開始迭代
    mapiternext(it)
}


func mapiternext(it *hiter) {
    h := it.h
    if raceenabled {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map iteration and map write")
    }
    t := it.t
    bucket := it.bucket
    b := it.bptr
    i := it.i
    checkBucket := it.checkBucket

next:
    // 如果當(dāng)前桶是nil励负，也就是說遍歷完了頭桶和對應(yīng)的所有溢出桶
    if b == nil {
        // 檢查是否遍歷了一圈回到了初始遍歷的那個桶
        // 以此來判斷是否遍歷結(jié)束
        if bucket == it.startBucket && it.wrapped {
            // end of iteration
            it.key = nil
            it.elem = nil
            return
        }
        // 如果在擴(kuò)容期間進(jìn)行的迭代
        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.
            // 找到對應(yīng)的舊桶
            // 因為擴(kuò)容期間饺蔑，舊桶有可能還沒有遷移到新桶略吨，那么我們就需要遍歷舊桶
            oldbucket := bucket & it.h.oldbucketmask()
            b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
            // 如果舊桶沒有遷移
            if !evacuated(b) {
                // 將舊桶和當(dāng)前桶映射起來
                checkBucket = bucket
            } else {
                // 否則就遍歷當(dāng)前桶
                b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
                // 標(biāo)記無舊桶需要遍歷
                checkBucket = noCheck
            }
        } else {
            // 如果沒有在擴(kuò)容秽之，同上
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
            checkBucket = noCheck
        }
        // 遍歷桶編號加1
        bucket++
        // 如果最后一個桶都遍歷完了河质，就回繞到頭桶并且打上回繞標(biāo)志
        if bucket == bucketShift(it.B) {
            bucket = 0
            it.wrapped = true
        }
        // 每次遍歷桶的時候，i都從0開始，用于遍歷該桶的8對kv
        i = 0
    }
    for ; i < bucketCnt; i++ {
        // 通過offset來打亂kv遍歷的順序
        offi := (i + it.offset) & (bucketCnt - 1)
        // 如果是空的，就跳過繼續(xù)遍歷下一對kv
        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))
        // 如果當(dāng)前遍歷的是舊桶并且不是等容量擴(kuò)容
        // 需要判斷舊桶的kv對應(yīng)到新桶是不是bucket號桶
        // 還記得擴(kuò)容遷移吧蛇捌，舊桶的kv遷移到新桶是可能落到前半部分和后半部分的
        // 如果當(dāng)前遍歷到的kv落到新桶不是bucket號桶，那就直接跳過了
        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).
            // 這里面區(qū)分兩種情況允粤，一種hash(k)是穩(wěn)定的
            // 另一種hash(k)是不穩(wěn)定的脑蠕，比如math.NaN()
            // 具體規(guī)則擴(kuò)容遷移的時候說過了，這里不贅述了
            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 which 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
                }
            }
        }
        // 如果當(dāng)前遍歷到的kv沒有遷移到新桶阐滩，則賦值給it饱溢，遍歷完成
        // 還有一種情況就是key!=key，比如上面說的math.NaN()，這種key沒法刪除和更新翁逞，也訪問不到(除了遍歷)
        // 所以不會被刪除必怜，可以直接取
        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).
            // 遍歷過程中，當(dāng)前k被刪除/更新/刪除后又重新插入等
            // 就需要重新找露久，具體怎么找征峦，mapaccessK后面會說
            rk, re := mapaccessK(t, h, k)
            if rk == nil {
                continue // key has been deleted
            }
            it.key = rk
            it.elem = re
        }
        // 保留迭代現(xiàn)場
        // 遍歷到哪個桶了迟几，實際遍歷的是哪個桶(可能新桶可能舊桶)，新舊桶是否有映射以及桶內(nèi)kv的遍歷進(jìn)度
        // 用于下次繼續(xù)遍歷
        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
    }
    // 當(dāng)前桶沒遍歷完了眶痰，繼續(xù)下一個溢出桶瘤旨，除了i其他不變
    b = b.overflow(t)
    i = 0
    // 繼續(xù)遍歷
    goto next
}


// returns both key and elem. Used by map iterator
// 比較簡單，其實就是通過key找到對應(yīng)的新桶好舊桶
// 如果舊桶沒有遷移就從舊桶找
// 否則就從新桶找
// 找的過程跟mapaccess1沒啥區(qū)別
// 就是一個桶一個桶的遍歷竖伯，遇到emptyRest就跳出外循環(huán)
// 然后對比k是否相等
// 這里就不詳細(xì)注釋了
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
    if h == nil || h.count == 0 {
        return nil, nil
    }
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)
bucketloop:
    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 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) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return k, e
            }
        }
    }
    return nil, nil
}

總結(jié)

至于總結(jié)存哲，就引用下這個吧，我寫累了七婴，需要休息會~