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

map[int64]int8

在這個例子中，如果按照 k/v/k/v/k/v/k/v 的形式存放的話，雖然每個鍵值對的值都只占用 1 個字節。但是卻需要 7 個填充字節來補齊內存空間。最終就會造成大量的內存 “浪費”

但是如果以 k/k/k/k/v/v/v/v 的形式存放的話，就能夠解決因對齊所 "浪費" 的內存空間

因此這部分的拆分主要是考慮到內存對齊的問題，雖然相對會復雜一點，但依然值得如此設計

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

而在 Go map 中當 hmap.buckets 滿了后，就會使用溢出桶接著存儲。我們結合分析可確定 Go 采用的是數組 + 鏈地址法解決哈希沖突

m := make(map[int32]int32)

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

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

makemap_small：當 hint 小于 8 時，會調用 makemap_small 來初始化 hmap。主要差異在于是否會馬上初始化 hash table

makemap64：當 hint 類型為 int64 時的特殊轉換及校驗處理，后續實質調用 makemap

makemap：實現了標準的 map 初始化動作

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
}

根據傳入的 bucket 類型，獲取其類型能夠申請的最大容量大小。并對其長度 make(map[k]v, hint) 進行邊界值檢驗

初始化 hmap

初始化哈希因子

根據傳入的 hint，計算一個可以放下 hint 個元素的桶 B 的最小值

分配并初始化 hash table。如果 B 為 0 將在后續懶惰分配桶，大于 0 則會馬上進行分配

返回初始化完畢的 hmap

在這里可以注意到，（當 hint 大于等于 8 ）第一次初始化 map 時，就會通過調用 makeBucketArray 對 buckets 進行分配。因此我們常常會說，在初始化時指定一個適當大小的容量。能夠提升性能。

若該容量過少，而新增的鍵值對又很多。就會導致頻繁的分配 buckets，進行擴容遷移等 rehash 動作。最終結果就是性能直接的下降（敲黑板）

而當 hint 小于 8 時，這種問題相對就不會凸顯的太明顯，如下：

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

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

在實現 map 元素訪問上有好幾種方法，主要是包含針對 32/64 位、string 類型的特殊處理，總的函數原型如下：

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 中，將返回對應類型的零值

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，長度是否為 0。若是則返回零值

判斷當前是否并發讀寫 map，若是則拋出異常

根據 key 的不同類型調用不同的 hash 方法計算得出 hash 值

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

判斷是否正在發生擴容（h.oldbuckets 是否為 nil），若正在擴容，則到老的 buckets 中查找（因為 buckets 中可能還沒有值，搬遷未完成），若該 bucket 已經搬遷完畢。則到 buckets 中繼續查找

計算 hash 的 tophash 值（高八位）

根據計算出來的 tophash，依次循環對比 buckets 的 tophash 值（快速試錯）

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

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

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

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

在本章節，我們介紹了 map 類型的以下知識點：

map 的基礎數據結構

初始化 map

訪問 map

從閱讀源碼中，得知 Go 本身對于一些不同大小、不同類型的屬性，包括哈希方法都有編寫特定方法去運行。總的來說，這塊的設計隱含較多的思路，有不少點值得細細品嘗 :)

注：本文基于 Go 1.11.5