本文在golang map 資料結構的基礎上，學習一個make 是如何構造的，
map 創建示例
在golang 中，初始化一個map 算是有兩種方式，
example1Map := make(map[int64]string)
example2Map := make(map[int64]string, 100)
第一種方式默認不指定map的容量，第二種會指定后續map的容量估計為100，希望在創建的時候把空間就分配好，
當make創建map時，底層做了什么
對于不同的初始化方式，會使用不同的方式，下面是提供的幾種初始化方法：
// hint 就是 make 初始化map 的第二個引數
func makemap(t *maptype, hint int, h *hmap) *hmap
func makemap64(t *maptype, hint int64, h *hmap) *hmap
func makemap_small() *hmap
區別在于：
如果不指定 hint，就呼叫makemap_small；
如果make 第二個引數為int64, 則呼叫makemap64；
其他情況呼叫makemap方法，下面我們逐一學習，
makemap_small
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
fastrand 是創建一個seed，在生成hash值時使用，
所以在makemap_small 時，只是創建了一個hmap 的結構體，并沒有初始化buckets.
makemap64
func makemap64(t *maptype, hint int64, h *hmap) *hmap {
if int64(int(hint)) != hint {
hint = 0
}
return makemap(t, int(hint), h)
}
makemap64 是對于傳入的第二個引數為int64 的變數使用的， 如果hint的值大于int最大值，就將hint賦值為0，否則和makemap 初始化沒有差別，為什么不把大于2^31 - 1 的map 直接初始化呢？因為在hmap 中 count 的值就是int，也就是說map最大就是 2^31 - 1 的大小，
makemap
這個是初始化map的核心代碼了，需要我們慢慢品味，
一開始，我們需要了解下maptype這個結構， maptype 標識一個map 資料型別的定義，當然還有其他的型別，比如說interfacetype，slicetype，chantype 等，maptype 的定義如下：
type maptype struct {
typ _type // type 型別
key *_type // key 的type
elem *_type // value 的type
bucket *_type // internal type representing a hash bucket
keysize uint8 // key 的大小
valuesize uint8 // value 的大小
bucketsize uint16 // size of bucket
flags uint32
}
maptype 里面存盤了kv的物件型別，bucket型別，以及kv占用記憶體的大小，以及bucketsize的大小，還有一些標記欄位（flags），在map 實作時，需要用到這些欄位做偏移計算等，
下面是 makemap 的代碼：
// hint 需要創建的 map 大小(預計要添加多少元素)
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
if h == nil {
h = new(hmap)
}
// xorshift64+ 演算法, 可以研究下
h.hash0 = fastrand()
// 計算B 的值
// 如果大于8，就先申請好，
// 申請規則就是剛好滿足 hint < 6.5 * 2 ^ B 的時候 （B 最大是63）
// 其中6.5 相當于每個bucket 鏈表中，平均有6.5個bucket
// 所以最長的map，應該是 6.5 * 2^63 (正常用肯定不會溢位)
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 接著資料初始化, 如果 容量小于等于8的，就在用的時候初始化, B 為0
if h.B != 0 {
var nextOverflow *bmap
// 申請一個buckets 陣列
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
首先，通過bucketsize 和hint 的值，計算出需要分配的記憶體大小mem， 以及是否會overflow （大于指標的最大地址范圍），如果溢位或者申請的記憶體大于最大可以申請的記憶體時，就設定hint為0了，直接不初始化buckets了，
接著，和makemap_small 一樣，初始化一個隨機的種子，
然后，計算B的值. 在overLoadfactor 中，判斷了hint 的大小，如果小于等于8，那B就不再賦值，直接不初始化資料，如果B大于8，那就計算B了，這里涉及到一個填充因子的概念，大概意思就是說，每個hash值（也就是pos）中，平均放多少個kv資料，默認是6.5；所以判斷標準就是hint 必須滿足如下的條件：
hint < 6.5 * (1 << B)
通過增加B的值，直到上面的運算式滿足為止，這樣B就初始化好了，
最后，申請一個bucket陣列，賦值給buckets，如果有多申請出來的buckets，那就賦值給extra.nextOverflow, 當溢位之后，從多申請出來的buckets 里面取（也是為了避免記憶體分配），
下面就詳細看下初始化一個buckets的構建，
makeBucketArray
makeBucketArray 用于初始化一個Bucket 陣列，也就是hmap 中的buckets，下面是相關代碼：
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// 為了防止溢位的遷移，加一點冗余的bucket
if b >= 4 {
// ... 修改nbuckets
}
// 如果之前沒有分配過，那直接分配
if dirtyalloc == nil {
buckets = newarray(t.bucket, int(nbuckets))
} else {
// 使用以前分配好的
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.kind&kindNoPointers == 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
if base != nbuckets {
// 處理多申請出來的bucket
}
return buckets, nextOverflow
}
這里用到了比較多的指標計算，需要細細品讀，
- 首先，就是就是通過B計算一個base值，base = 1 << B （2 ^ B)
nbuckets 是需要申請的陣列的長度，正常情況下 base 值就是陣列長度，但是，如果 base 大于16時，會預分配一些需要后期做overflow的bucket，這個overflow的計算規則如下：
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
在base 的基礎上，多分配 base / 16 長度的bucket，然后根據記憶體的分配規則（包括了頁大小和記憶體對齊等規則），計算出合適的分配記憶體的大小，然后計算出 bucket 的分配個數 nbuckets.
-
其次，如果有之前未分配記憶體，那就初始化一個陣列（終于等到了這一步），如過有dirtyalloc， 那就使用dirtyalloc 的記憶體（其實是用來清除map中資料使用的），然后把dirtyalloc中不需要的資料清除參考，
-
最后，如果除了需要申請的base 長度的bucket外，還多申請了一些bucket，下面是對多申請的資料做的處理：
// 上面添加了一些nbuckets 防止溢位，所以B 值取模就不太合理了，所以有一個mapextra 的資料節點
// 資料分配也很有趣，從剛申請的buckets陣列中，取出后面的一段分給mapextra
// nextOverflow 分配給mapextra
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
// 取nextOverflow 里面的最后一個元素，并把最后一個buckets 的末尾偏移的指標指向空閑的bucket (目前就是第一個buckets 了)
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
先計算出多申請出來的記憶體地址 nextOverflow，然后計算出 申請的最后一塊bucket的地址，然后將最后一塊bucket的overflow指標（指向鏈表的指標）指向buckets 的首部， 原因呢，是為了將來判斷是否還有空的bucket 可以讓溢位的bucket空間使用，
今天的作業就交完了，下一篇將學習golang map的資料初始化實作，
參考
[1] 深入理解 Go map:初始化和訪問
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20852.html
標籤：Go
上一篇：Golang Map實作（一）