一文啃透 Go map：初始化和訪問

大家好，我是煎魚。

咱們一起探索 Go 語言 map 裏面的奧妙吧，看看它的內在是怎麼構成的，又分別有什麼值得留意的地方？

本文將探討初始化和訪問元素相關板塊，咱們帶着疑問去學習，例如：

數據結構

首先我們一起看看 Go 語言中 map 的基礎數據結構，先有一個大致的印象

hmap 基本結構

hmap

type hmap struct {
 count     int
 flags     uint8
 B         uint8
 noverflow uint16
 hash0     uint32
 buckets    unsafe.Pointer
 oldbuckets unsafe.Pointer
 nevacuate  uintptr
 extra *mapextra
}

type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap
 nextOverflow *bmap
}

在這裏我們要注意幾點，如下：

  1. 如果 keys 和 values 都不包含指針並且允許內聯的情況下。會將 bucket 標識爲不包含指針，使用 extra 存儲溢出桶就可以避免 GC 掃描整個 map，節省不必要的開銷

  2. 在前面有提到，Go 用了增量擴容。而 buckets 和 oldbuckets 也是與擴容相關的載體，一般情況下只使用 buckets，oldbuckets 是爲空的。但如果正在擴容的話，oldbuckets 便不爲空，buckets 的大小也會改變

  3. 當 hint 大於 8 時，就會使用 *mapextra 做溢出桶。若小於 8，則存儲在 buckets 桶中

bmap

bmap 基本結構

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits
...
type bmap struct {
 tophash [bucketCnt]uint8
}

實際 bmap 就是 buckets 中的 bucket，一個 bucket 最多存儲 8 個鍵值對

tophash

tophash 是個長度爲 8 的數組，代指桶最大可容納的鍵值對爲 8。

存儲每個元素 hash 值的高 8 位，如果 tophash [0] <minTopHash，則 tophash [0] 表示爲遷移進度

keys 和 values

在這裏我們留意到，存儲 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 的形式存放的話，就能夠解決因對齊所 "浪費" 的內存空間

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

overflow

可能會有同學疑惑爲什麼會有溢出桶這個東西？實際上在不存在哈希衝突的情況下，去掉溢出桶，也就是隻需要桶、哈希因子、哈希算法。也能實現一個簡單的 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

源碼

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
}

在這裏可以注意到（當 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
...

源碼

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])
}

在上述步驟三中，提到了根據不同的類型計算出 hash 值，另外會計算出 hash 值的高八位和低八位。

低八位會作爲 bucket index，作用是用於找到 key 所在的 bucket。而高八位會存儲在 bmap tophash 中

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

圖示

總結

我們介紹了 map 類型的以下知識點：

從閱讀源碼中，得知 Go 本身對於一些不同大小、不同類型的屬性，包括哈希方法都有編寫特定方法去運行。

總的來說，這塊的設計隱含較多的思路，有不少點值得細細品嚐 ：）

你覺得 Go map 設計的怎麼樣呢？

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/iL9dgMW47q0ySTYkvfl6fg

猜你喜歡