在這里我們留意到，存儲(chǔ) k 和 v 的載體并不是用 k/v/k/v/k/v/k/v 的模式，而是 k/k/k/k/v/v/v/v 的形式去存儲(chǔ)。這是為什么呢？

map[int64]int8

在這個(gè)例子中，如果按照 k/v/k/v/k/v/k/v 的形式存放的話，雖然每個(gè)鍵值對(duì)的值都只占用 1 個(gè)字節(jié)。但是卻需要 7 個(gè)填充字節(jié)來(lái)補(bǔ)齊內(nèi)存空間。最終就會(huì)造成大量的內(nèi)存 “浪費(fèi)”

但是如果以 k/k/k/k/v/v/v/v 的形式存放的話，就能夠解決因?qū)R所 "浪費(fèi)" 的內(nèi)存空間

因此這部分的拆分主要是考慮到內(nèi)存對(duì)齊的問(wèn)題，雖然相對(duì)會(huì)復(fù)雜一點(diǎn)，但依然值得如此設(shè)計(jì)

可能會(huì)有同學(xué)疑惑為什么會(huì)有溢出桶這個(gè)東西？實(shí)際上在不存在哈希沖突的情況下，去掉溢出桶，也就是只需要桶、哈希因子、哈希算法。也能實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 hash table。但是哈希沖突（碰撞）是不可避免的...

而在 Go map 中當(dāng) hmap.buckets 滿了后，就會(huì)使用溢出桶接著存儲(chǔ)。我們結(jié)合分析可確定 Go 采用的是數(shù)組 + 鏈地址法解決哈希沖突

m := make(map[int32]int32)

通過(guò)閱讀源碼可得知，初始化方法有好幾種。函數(shù)原型如下：

func makemap_small() *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap

makemap_small：當(dāng) hint 小于 8 時(shí)，會(huì)調(diào)用 makemap_small 來(lái)初始化 hmap。主要差異在于是否會(huì)馬上初始化 hash table

makemap64：當(dāng) hint 類(lèi)型為 int64 時(shí)的特殊轉(zhuǎn)換及校驗(yàn)處理，后續(xù)實(shí)質(zhì)調(diào)用 makemap

makemap：實(shí)現(xiàn)了標(biāo)準(zhǔn)的 map 初始化動(dòng)作

func makemap(t *maptype, hint int, h *hmap) *hmap {
    if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
        hint = 0
    }

    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()

    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    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
}

根據(jù)傳入的 bucket 類(lèi)型，獲取其類(lèi)型能夠申請(qǐng)的最大容量大小。并對(duì)其長(zhǎng)度 make(map[k]v, hint) 進(jìn)行邊界值檢驗(yàn)

初始化 hmap

初始化哈希因子

根據(jù)傳入的 hint，計(jì)算一個(gè)可以放下 hint 個(gè)元素的桶 B 的最小值

分配并初始化 hash table。如果 B 為 0 將在后續(xù)懶惰分配桶，大于 0 則會(huì)馬上進(jìn)行分配

返回初始化完畢的 hmap

在這里可以注意到，（當(dāng) hint 大于等于 8 ）第一次初始化 map 時(shí)，就會(huì)通過(guò)調(diào)用 makeBucketArray 對(duì) buckets 進(jìn)行分配。因此我們常常會(huì)說(shuō)，在初始化時(shí)指定一個(gè)適當(dāng)大小的容量。能夠提升性能。

若該容量過(guò)少，而新增的鍵值對(duì)又很多。就會(huì)導(dǎo)致頻繁的分配 buckets，進(jìn)行擴(kuò)容遷移等 rehash 動(dòng)作。最終結(jié)果就是性能直接的下降（敲黑板）

而當(dāng) hint 小于 8 時(shí)，這種問(wèn)題相對(duì)就不會(huì)凸顯的太明顯，如下：

func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

v := m[i]
v, ok := m[i]

在實(shí)現(xiàn) map 元素訪問(wèn)上有好幾種方法，主要是包含針對(duì) 32/64 位、string 類(lèi)型的特殊處理，總的函數(shù)原型如下：

mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)

mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer
mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool)

mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
...

mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
...

mapaccess1：返回 h[key] 的指針地址，如果鍵不在 map 中，將返回對(duì)應(yīng)類(lèi)型的零值

mapaccess2：返回 h[key] 的指針地址，如果鍵不在 map 中，將返回零值和布爾值用于判斷

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    alg := t.key.alg
    hash := alg.hash(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)
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            if alg.equal(key, k) {
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

判斷 map 是否為 nil，長(zhǎng)度是否為 0。若是則返回零值

判斷當(dāng)前是否并發(fā)讀寫(xiě) map，若是則拋出異常

根據(jù) key 的不同類(lèi)型調(diào)用不同的 hash 方法計(jì)算得出 hash 值

確定 key 在哪一個(gè) bucket 中，并得到其位置

判斷是否正在發(fā)生擴(kuò)容（h.oldbuckets 是否為 nil），若正在擴(kuò)容，則到老的 buckets 中查找（因?yàn)?buckets 中可能還沒(méi)有值，搬遷未完成），若該 bucket 已經(jīng)搬遷完畢。則到 buckets 中繼續(xù)查找

計(jì)算 hash 的 tophash 值（高八位）

根據(jù)計(jì)算出來(lái)的 tophash，依次循環(huán)對(duì)比 buckets 的 tophash 值（快速試錯(cuò)）

如果 tophash 匹配成功，則計(jì)算 key 的所在位置，正式完整的對(duì)比兩個(gè) key 是否一致

若查找成功并返回，若不存在，則返回零值

在上述步驟三中，提到了根據(jù)不同的類(lèi)型計(jì)算出 hash 值，另外會(huì)計(jì)算出 hash 值的高八位和低八位。低八位會(huì)作為 bucket index，作用是用于找到 key 所在的 bucket。而高八位會(huì)存儲(chǔ)在 bmap tophash 中

其主要作用是在上述步驟七中進(jìn)行迭代快速定位。這樣子可以提高性能，而不是一開(kāi)始就直接用 key 進(jìn)行一致性對(duì)比

在本章節(jié)，我們介紹了 map 類(lèi)型的以下知識(shí)點(diǎn)：

map 的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

初始化 map

訪問(wèn) map

從閱讀源碼中，得知 Go 本身對(duì)于一些不同大小、不同類(lèi)型的屬性，包括哈希方法都有編寫(xiě)特定方法去運(yùn)行?？偟膩?lái)說(shuō)，這塊的設(shè)計(jì)隱含較多的思路，有不少點(diǎn)值得細(xì)細(xì)品嘗 :)

注：本文基于 Go 1.11.5