MAP底層原理分析

參考

1. https://golang.design/go-questions/map/principal
2. map | Golang 中文學習文檔

---

1. 先來看一下map結構體，（runtime.hmap結構體就是代表著 go 中的map，與切片一樣map的內部實現也是結構體）

   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.count     int // # live cells == size of map.  Must be first (used by len() builtin)flags     uint8B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0     uint32 // hash seedbuckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growingnevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)clearSeq   uint64extra *mapextra // optional fields
   }
   

   內部實現圖

簡單說明一下各個字段含義

• count：表示 hamp 中的元素數量，結果等同于len(map)

• flags : hmap 的標志位，用于表示 hmap 處于什么狀態，有以下幾種可能

  const (iterator     = 1 // 迭代器正在使用桶oldIterator  = 2 // 迭代器正在使用舊桶hashWriting  = 4 // 一個協程正在寫入hmapsameSizeGrow = 8 // 正在等量擴容
  )
  

• B：hmap 中的哈希桶的數量為1 << B

• noverflow，hmap 中溢出桶的大致數量。

• 哈希種子，在 hmap 被創建時指定，用于計算哈希值。

• buckets，存放哈希桶數組的指針。

• oldbuckets，存放 hmap 在擴容前哈希桶數組的指針。

• extra，存放著 hmap 中的溢出桶，溢出桶指的是就是當前桶已經滿了，創建新的桶來存放元素，新創建的桶就是溢出桶。

  type mapextra struct {// 溢出桶的指針切片overflow    *[]*bmap// 擴容前舊的溢出桶的指針切片oldoverflow *[]*bmap// 指向下一個空閑的溢出桶的指針nextOverflow *bmap
  }
  

2. 一直說的桶是個什么東西 ？

   hamp 中的buckets也就是桶切片指針，在 go 中對應的結構為runtime.bmap，如下所示

   // A bucket for a Go map.
   type bmap struct {tophash [abi.OldMapBucketCount]uint8
   }
   // OldMapBucketCount是如下的這個變量
   // Maximum number of key/elem pairs a bucket can hold.
   OldMapBucketCountBits = 3 // log2 of number of elements in a bucket.
   OldMapBucketCount     = 1 << OldMapBucketCountBits // 默認為8
   

   表面上看，它只有一個字段tophash，不過實際上來說，bmap的字段不止這些，這是因為map可以存儲各種類型的鍵值對，所以需要在編譯時根據類型來推導占用的內存空間，在cmd/compile/internal/reflectdata/reflect.go中的MapBucketType函數的功能就是在編譯時構造 bmap，它會進行一系列檢查工作，比如 key 的類型是否comparable。

   // MapBucketType makes the map bucket type given the type of the map.
   func MapBucketType(t *types.Type) *types.Type
   

   bmap內部結構：HOB Hash 指的就是 top hash。

實際上bmap結構如下；不過這些字段對我們是不可見的，go 在實際操作中是通過移動 unsafe 指針來進行訪問

// 實際運行時定義（簡化為可理解的結構）
type bmap struct {// 哈希值高8位數組 (每個槽位1字節)tophash [abi.OldMapBucketCount]uint8  // bucketCnt = 8// 以下是隱式字段（編譯器在編譯時根據鍵值類型動態生成內存布局）keys    [abi.OldMapBucketCount]keyType   // 鍵數組（連續存儲）elems   [abi.OldMapBucketCount]elemType  // 值數組（連續存儲）注意：1.17+ 改名為 elems// 溢出桶指針（重要：在 keys/elems 之后存儲）overflow *bmap
}
// 注意:有些文章還有pad字段 ，該字段是為了保持內存對齊，提高一些操作的效率的

tophash字段是什么 ？

首先，根據字面意思就是一個為uint8類型的長度為 8的數組 ，此時也就定義了 一個桶中可以存放8個鍵值對，桶中每個元素是uint8，代表每個鍵（key）對應的hash值得高八位， 用于定位該鍵（key）在本桶的位置。

另外，tophash還有一些特殊的值，通常是處于擴容的遷移狀態下：

const (emptyRest      = 0 // 當前元素是空的，并且該元素后面也沒有可用的鍵值了emptyOne       = 1 // 當前元素是空的，但是該元素后面有可用的鍵值。evacuatedX     = 2 // 擴容時出現，只能出現在oldbuckets中，表示當前元素被搬遷到了新哈希桶數組的上半區evacuatedY     = 3 // 擴容時出現只能出現在oldbuckets中，表示當前元素被搬遷到了新哈希桶數組的下半區evacuatedEmpty = 4 // 擴容時出現，元素本身就是空的，在搬遷時被標記minTopHash     = 5 // 對于一個正常的鍵值來說tophash的最小值
)

• minTopHash：當一個 cell（每個tophash元素抽象成每一個cell） 的 tophash 值小于 minTopHash 時，標志這個 cell 的遷移狀態。因為這個狀態值是放在 tophash 數組里，為了和正常的哈希值區分開，會給 key 計算出來的哈希值一個增量：minTopHash。這樣就能區分正常的 top hash 值和表示狀態的哈希值
• 其余變量是遷移過程中用到的 ，后續說明

3. key定位過程

   參考文章中說明的很好：

   ---

   key 經過哈希計算后得到哈希值，共 64 個 bit 位（64位機，32位機就不討論了，現在主流都是64位機），計算它到底要落在哪個桶時，只會用到最后 B 個 bit 位。還記得前面提到過的 B 嗎？如果 B = 5，那么桶的數量，也就是 buckets 數組的長度是 2^5 = 32。

   例如，現在有一個 key 經過哈希函數計算后，得到的哈希結果是：

    10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
   

   用最后的 5 個 bit 位，也就是 01010，值為 10，也就是 10 號桶。這個操作實際上就是取余操作，但是取余開銷太大，所以代碼實現上用的位操作代替。

   再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，這是在尋找已有的 key。最開始桶內還沒有 key，新加入的 key 會找到第一個空位，放入。

上圖中，假定 B = 5，所以 bucket 總數就是 2^5 = 32。首先計算出待查找 key 的哈希，使用低 5 位 00110，找到對應的 6 號 bucket，使用高 8 位 10010111，對應十進制 151，在 6 號 bucket 中尋找 tophash 值（HOB hash）為 151 的 key，找到了 2 號槽位，這樣整個查找過程就結束了。

如果在 bucket 中沒找到，并且 overflow 不為空，還要繼續去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

---

key與value的定位方法

// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))// value 定位公式
e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))

b 是 bmap 的地址，這里 bmap 還是源碼里定義的結構體，只包含一個 tophash 數組，經編譯器擴充之后的結構體才包含 key，value，overflow 這些字段。dataOffset 是 key 相對于 bmap 起始地址的偏移， 也就是bmap中key地址開始的位置：

dataOffset = unsafe.Offsetof(struct {b bmapv int64}{}.v)

當定位到一個具體的 bucket 時，里層循環就是遍歷這個 bucket 里所有的 cell，或者說所有的槽位，也就是 bucketCnt=8 個槽位。整個循環過程：

遍歷過程中會判斷每一個cell的狀態 ，判斷這個bucket是否搬遷完畢，源碼中用到的函數

func evacuated(b *bmap) bool {h := b.tophash[0]return h > empty && h < minTopHash
}

只取了 tophash 數組的第一個值，判斷它是否在 0-4 之間。對比上面的常量，當 top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 這三個值之一，說明此 bucket 中的 key 全部被搬遷到了新 bucket。